Erdős problem #617 · graph theory · session 2026-08-27
Take twenty-five people, and give every pair of them one of five colours. Now pick any six of those people. Between six people there are fifteen pairs. The colouring is called balanced if those fifteen pairs always show all five colours, no matter which six people you picked.
Twenty-five people can be done. The recipe is a piece of geometry: arrange the twenty-five as a 5 by 5 grid, and colour each pair by the direction of the line joining them. Any six points must contain two lying on a common line in every direction, so every colour turns up. That is the figure below, and you can check it exhaustively yourself, in your browser, over all 177,100 ways of choosing six.
Twenty-six people is the question. In 1999 Erdős and Gyárfás conjectured that you cannot do it: with five colours, twenty-five is the ceiling, and the same ceiling of r² should hold for every number of colours r ≥ 3. They proved it for three colours and for four. For five colours nobody knows, and that is where this note works.
The conjecture has been open at five colours since 1999, and no computational attack on it appears in the literature. This session built the structural map around the single undecided instance rather than deciding it. Six things came out:
Everything below is the technical version. The two figures that carry the argument fastest are the counting barrier in section 4 and the symmetry exhaustion in section 5, both of which recompute their result in the browser.
An edge r-colouring of KN is balanced if every set of r+1 vertices spans all r colours. Erdős and Gyárfás conjectured that for r ≥ 3 the complete graph Kr²+1 admits no balanced r-colouring; the case r = 5, that is K26, is the first open one. We record a structural and computational map of that case.
On the constructive side, codes with pairwise agreement at most one give balanced colourings, and the Reed–Solomon code of an affine plane yields T(r) ≥ r² for every prime power r; the r = 5 witness on K25 is verified from the definition over all 177,100 six-subsets. On the obstruction side, a two-line argument shows every colour class of a hypothetical K26 witness is a (6,6)-Ramsey graph, which empties the partition-structured sector. Writing E*(N,s) for the maximum number of edges of a graph on N vertices with no Ks and no independent s-set, existence at Kr²+1 forces E*(r²+1, r+1) ≥ (r−1)/r · C(r²+1, 2). We compute E*(10,4) = 31 against a threshold of 30, E*(17,5) ≥ 104 against 102, and E*(26,6) ≥ 265 against 260, so this counting barrier is sharp but never binding for r ≥ 3, while at r = 2 it is met with equality by the genuine counterexample C₅. Two witness families are then excluded at K26: the affine family does not extend (UNSAT, with a 1,160-line DRUP proof independently checked), and no vertex-regular colouring exists (profile arithmetic over Z26, and an exhaustive check of all 3,198 admissible D13 classes). Finally the direct decision instance is observed to be pigeonhole-hard for CDCL and cutting-planes solvers alike.
The K26 decision itself remains open. Nothing here should be read as progress toward either verdict; it is a map of which routes are now closed.
An edge r-colouring of KN is balanced if no (r+1)-clique misses a colour. Write T(r) for the largest N admitting a balanced r-colouring. The property is monotone: restricting a balanced colouring to N−1 vertices leaves it balanced, since every (r+1)-subset of the restriction is one of KN. The conjecture is that T(r) ≤ r² for r ≥ 3. For r = 2 it is false, with T(2) = 5, reproduced here end to end as a control (215 exhaustion and SAT in both directions).
For a colouring, let Gc be the graph of c-coloured edges and Hc its complement in KN. Then balanced is equivalent to α(Gc) ≤ r for every c, equivalently every Hc is Kr+1-free.
In a balanced r-colouring of KN, every colour class satisfies |Gc| ≥ C(N,2) − ex(N; Kr+1), because Hc is Kr+1-free. At N = 26, r = 5 we have ex(26; K₆) = e(T₅(26)) = 270, so every colour class carries at least 55 of the 325 edges.
In a balanced r-colouring with r ≥ 2, every monochromatic clique has at most r vertices, since an all-c set of r+1 vertices would miss the other r−1 colours. Hence every Hc has independence number at most r, and at N = r²+1, χ(Hc) ≥ N/α(Hc) ≥ (r²+1)/r > r. So every Hc is Kr+1-free with chromatic number at least r+1.
At N = r²+1 no colour-class complement Hc is r-partite. An r-partition of the vertices into Hc-independent parts would be a partition into at most r monochromatic c-cliques of size at most r each, covering at most r² < r²+1 vertices.
Fact A also explains r = 2 cleanly. The K₅ witness has Hc = C₅ with χ(C₅) = 3 = r+1, so the conjecture for r ≥ 3 is precisely the assertion that this odd-cycle escape has no higher analogue.
Let C be a set of N words of length r over an r-letter alphabet, pairwise agreeing in at most one coordinate. Then KN has a balanced r-colouring: identify vertices with words, let coordinate c partition the vertices by their c-th letter, and colour each pair by the (unique, if any) coordinate in which the two words agree, colouring never-agreeing pairs arbitrarily. Any r+1 vertices take at most r values in coordinate c, so two agree there by pigeonhole and that edge has colour c.
For a prime power r the evaluation code {(ax+b)x∈Fr} (the [r,2,r−1]r Reed–Solomon code) has r² words agreeing pairwise in at most one place, since distinct affine polynomials agree at most once. Equivalently: take the points of AG(2,r), colour each edge by the parallel class of the line through its endpoints, and merge two of the r+1 classes. Every (r+1)-set contains two points on a common line of every parallel class, because r+1 points distribute over r lines. Machine-verified from the definition for r = 3, 4, 5 over all 126, 4,368 and 177,100 subsets respectively.
Remark (converse, Singleton and MOLS). If every Hc is r-partite, then fixing a partition into at most r c-cliques per colour and sending each vertex to its r-tuple of part indices produces N words with pairwise agreement at most one, since an edge co-partitioned twice would need two colours. So partition-structured balanced colourings are exactly the code colourings of Lemma 2, and the Singleton bound caps them at N ≤ r². That is a second proof of Corollary A1. At N = r² the equivalence becomes "structured witness ⟺ OA(r², r, r, 2) ⟺ r−2 MOLS(r)", which links the Kr² cases to the existence problem for mutually orthogonal Latin squares; for r = 6, Tarry's theorem denies even 2 MOLS(6), consistent with the recorded remark that Kr² fails for infinitely many r. Whether this correspondence is already in the 1999 paper could not be checked here (see the caveats).
By Fact A and Lemma 1, in any balanced 5-colouring of K26 every colour class Gc has at least 55 of the 325 edges, ω(Gc) ≤ 5 and α(Gc) ≤ 5, and every complement Hc is a K₆-free graph with χ(Hc) ≥ 6 and between 220 and 270 edges. Graphs like that exist in isolation: C₅ ∨ K₃ is K₆-free with chromatic number 6 on eight vertices. So no per-class argument can close the problem, and the entire content lies in the joint edge-partition. Each class is a Ramsey-type graph with no K₆ and no independent six-set, which is what makes the extremal quantity of the next section the right thing to compute.
Define E*(N, s) as the maximum number of edges of a graph on N vertices containing no Ks and no independent set of size s. In a balanced r-colouring of Kr²+1, with s = r+1 and N = r²+1, every Hc is such a graph, so C(N,2) = Σc |Gc| ≥ r·(C(N,2) − E*(N, r+1)), which rearranges to a necessary condition.
If the extremal number were to fall below its threshold, the conjecture would follow immediately for that r. It does not, and the margins are the interesting part.
| quantity | value | threshold | margin | status |
|---|---|---|---|---|
| E*(5,3) | = 5 (C₅, classical) | 5 | 0 | anchor: met with equality, and realized |
| E*(10,4) | = 31 | 30 | +1 | CERTIFIED witness at 31, UNSAT at 32 in 4.6 s |
| E*(17,5) | ≥ 104 | 102 | ≥ +2 | CERTIFIED lower bound; ≤ 108 trivially |
| E*(26,6) | ≥ 265 | 260 | ≥ +5 | CERTIFIED lower bound; ≤ 269 |
| max circulant on Z₂₆, no K₆ or I₆ | 221 edges | 260 | −39 | CERTIFIED exhaustive over all 213 connection sets |
The upper bounds come from Turán uniqueness: a 270-edge K₆-free graph on 26 vertices must be T₅(26), whose six-element part is an independent six-set, so E*(26,6) ≤ 269; the same argument gives E*(17,5) ≤ 107. The brackets that stand at the end of the session are therefore E*(17,5) ∈ [104, 107] and E*(26,6) ∈ [265, 269].
If E*(26,6) were exactly 260, then every colour class of a K26 witness would carry exactly 65 edges with every complement extremal, since Σ|Gc| = 325 = 5·(325−260) forces equality throughout. That premise was refuted the same day: E*(26,6) ≥ 261, then ≥ 265, both witnesses committed and verified from the definition. What survives is the weaker range |Gc| ∈ [325 − E*(26,6), 105], that is classes of 56 to 60 edges at minimum once E* is pinned, still above the naive Turán floor of 55. The r = 2 anchor shows the rigidity scenario is not vacuous: there it does hold, and it produces the counterexample.
Colour K25 on the points of AG(2,5) using five of the six parallel classes, leaving the 50 pairs of the sixth class free; every choice is balanced, since the pigeonhole uses only the five kept classes. No choice of those 50 free colours, together with any colouring of the 25 edges at a new vertex, makes K26 balanced. The instance has 375 variables and 16,450 clauses (only six-sets through the new vertex constrain it) and is UNSAT, with a 1,160-line DRUP proof checked by the repository's independent verifier. The same pipeline at q = 2, taking the K₄ family to K₅, finds the 2 known C₅-type extensions, as a positive control.
In a group-invariant balanced 5-colouring of K26 by a regular action, each colour class is a union of Cayley edge-classes. With a rotation classes (26 edges each) and b involution classes (13 edges each) per colour, Lemma 1 forces 2a + b ≥ 5 for every colour, while Σc(2ac + bc) = 25 forces equality, so every colour class has exactly 65 edges. Over Z26 the equation 2a + b = 5 with b ∈ {0,1} per colour and Σb = 1 is unsolvable, so there is no Z26-circulant witness. Over D13 the admissible profiles are (a,b) ∈ {(2,1), (1,3), (0,5)}.
No D13-invariant balanced 5-colouring of K26 exists. Of the 195 + 1,716 + 1,287 = 3,198 candidate colour classes admitted by Lemma 6, not one has independence number at most 5. A fortiori no exact cover into five such classes exists.
Remark. Any 2-transitive symmetry is impossible trivially, since a 2-transitive group has a single orbital and the colouring would be monochromatic. The contrast with r = 2 is the point: the vertex-regular escape that produces the r = 2 counterexample provably has no analogue at r = 5.
The natural CNF for "KN has a balanced r-colouring", one exactly-one-colour constraint per edge plus one coverage clause per ((r+1)-set, colour) pair, is already impractical for CDCL at K10 with r = 3: 135 variables and 810 clauses, and yet CaDiCaL 1.9.5, Glucose 4.2 and kissat 4.0.4 all run for minutes to hours unaided, while the cutting-planes solver RoundingSat exceeds 120 s on the equivalent pseudo-Boolean model. The refutations are pigeonhole-like counting arguments, which resolution cannot do in polynomial size. With BreakID 3 symmetry-breaking predicates for SN × Sr, that same K10 instance is UNSAT in 3.1 s, which reproduces the Erdős–Gyárfás r = 3 theorem by machine.
Certification caveat: the symmetry-breaking predicates are trusted, being satisfiability-preserving by construction rather than derived in the proof system, so this reproduction is labelled CERTIFIED (modulo BreakID) and not more. The DRUP-certified result in this note is Lemma 5.
| instance | window | outcome |
|---|---|---|
| K₁₀, r = 3, symmetry-broken | — | UNSAT in 3.1 s, the r = 3 theorem reproduced |
| K₁₇, r = 4, broken + cardinality | 3 h and 70 min | unknown, even the proved r = 4 case resists at this scale |
| K₂₆, r = 5, broken + cardinality | 3 h | unknown, the open case is beyond a four-core day by direct SAT |
| E*(17,5) ≥ 106 and ≥ 108 | 20 min each | unknown, leaving the bracket [104, 107] |
| E*(26,6) ≥ 266, 267, 269 | 60 to 90 min each | unknown, leaving the bracket [265, 269] |
All runs on kissat 4.0.4 over BreakID-broken instances, four cores. These are wall-clock observations on one machine, labelled NUMERICAL, and are not a lower-bound theorem.