#617: the exact edge floor for every candidate color class

The target (erdosproblems.com/617, FALSIFIABLE). Erdős and Gyárfás conjectured that every coloring of the edges of K_r²+1 with r colors has r+1 vertices whose induced clique misses at least one color. They proved this for r=3 and r=4. We do not prove the next case r=5.

The color-class reduction. Suppose instead that a balanced coloring exists, meaning every (r+1)-vertex clique contains every color. Fix one color and let G be the graph formed by its edges. An independent set of size r+1 would miss that color. A clique of size r+1 would use only that color and miss all the others. Therefore every color graph must satisfy

α(G)≤r and ω(G)≤r.

We determined the exact cheapest possible graph with those two properties. For every integer r≥2, define

m_r=min{e(G): |V(G)|=r²+1, α(G),ω(G)≤r}.

Then

m_r=(r³−r²+4r−2)/2.

The lower bound. Put H equal to the complement of G. The bound α(G)≤r says H is K_r+1-free. Meanwhile α(H)=ω(G)≤r, so coloring the r²+1 vertices of H requires at least r+1 colors; H is not r-partite.

Kang and Pikhurko's exact stability theorem determines the largest edge count of precisely such a graph. At n=r²+1 their Theorem 1 gives

e(H)≤t_r(n)−⌊n/r⌋+1 =t_r(n)−r+1,

where t_r(n) is the balanced Turán number. Its part sizes are r+1,r,...,r. Complementing and simplifying gives e(G)≥(r³−r²+4r−2)/2.

A construction attaining it. Start with K_r,r+1 on parts X and Y. Choose y₁,y₂ in Y, add the edge y₁y₂, and for every x in X delete exactly one of xy₁,xy₂, using both deletion choices. Call the resulting graph J. It has r²+1 edges, is triangle-free, and has α(J)=r.

Now take the disjoint union of r−2 copies of K_r and the complement of J. This graph has r²+1 vertices, exactly the displayed number of edges, and both clique and independence number r. For r=2 the clique part is empty and the construction is simply C₅.

What this says at r=5. Every one of the five color classes in a counterexample on K₂₆ would need at least

m₅=59 edges.

The lower bounds consume 5·59=295 of the 325 edges. More generally the unallocated slack is exactly r(r−1)(r−2)/2; at r=5 it is 30. That gap matters: this theorem constrains each color separately but does not show whether five such graphs can partition K₂₆.

Audit posture. The lower proof depends only on the published Kang–Pikhurko theorem, whose exact hypotheses and both parameter branches were checked against the official paper. The upper construction is elementary. At r=5, two independent standard-library checkers start from different graph representations and verify 59 edges, clique number 5, and independence number 5; one directly exhausts all 230,230 six-vertex subsets. A third checker tests the general construction and polynomial identities, while the written case proof supplies the universal quantifier. An ultra cold audit reproduced the bundle and caught the r=2 wording boundary before publication.

Scope. This is a derived auxiliary consequence, not a claim of literature priority for a resolution of #617. The site also had a May 2026 ledger attempt concerning affine K₂₅ extensions; this is a separate second round. The simultaneous color-partition problem, including r=5, remains open.