An explicit 94-vertex cubic-residue candidate and certificate reduction

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph. It is $K_4$-free if no four distinct vertices have all six possible edges between them. Write $G\to(K_3,K_3)$ if for every map $c:E\to\{\mathrm{red},\mathrm{blue}\}$ there are distinct vertices $u,v,w$ whose three pairwise edges belong to $E$ and receive the same color. Such a coloring is an edge coloring; there is no proper-coloring requirement. A graph satisfying both properties is an edge Folkman graph for triangles with forbidden clique $K_4$.

The workshop challenge is to construct such a graph on fewer than $100$ vertices. Equivalently, if \[ F_e(3,3;4)=\min\{|V(G)|:G\text{ is }K_4\text{-free and } G\to(K_3,K_3)\}, \] the proposed target is $F_e(3,3;4)\le99$. A complete construction must specify all vertices and edges and verify both requirements. Verifying the absence of $K_4$ alone is insufficient: the Ramsey condition quantifies over every two-coloring of the edges. Conversely, a graph with the Ramsey property but containing a $K_4$ does not qualify. Vertices or edges removed from a larger candidate must be accounted for in the verification, since deleting them may destroy the Ramsey property. If the numerical target is impossible, a proof that every graph on at most $99$ vertices fails at least one condition would decide the challenge negatively.

Short English statement

Find a graph on at most 99 vertices with no four-clique that forces a monochromatic triangle in every two-coloring of its edges.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20000962 (AIM-COMBINATORICS-0087), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Graph Ramsey theory, item 40. Original workshop question underlying AIM-COMBINATORICS-0087. https://www.overleaf.com/read/mnvcscjjysvg.