Fabian Arevalo

Erdős problem #617 · graph theory · session 2026-08-27

Balanced colourings of complete graphs, at the first open case

A certified balanced 5-colouring of K25, a proof that the natural counting barrier is sharp yet never binding for r ≥ 3, and two certified exclusions at K26. The K26 question itself is left open.
27 August 2026 · AI-assisted (Claude), see disclosure · code, data and certificates

Start here, no maths required

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.

every panel below is non-empty
The balanced 5-colouring of K25, computed live. Twenty-five points on the 5 by 5 grid of the affine plane AG(2,5). Six are highlighted, and the fifteen pairs between them are drawn. The strip beneath splits those fifteen pairs by colour, one panel per colour: the colouring is balanced exactly when no panel is ever empty. Press New six to move the subset, or run the exhaustive check over all 177,100 six-subsets. This is not a stored picture: the colouring is rebuilt from the geometry each time the figure draws, and it agrees edge for edge with the witness committed in the repository.

What this note adds

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:

  1. Twenty-five is achievable, certified. The affine construction gives a balanced r-colouring of Kr² for every prime power r, verified from the definition over all 177,100 six-subsets at r = 5 (and 4,368 at r = 4, 126 at r = 3). So the whole question really does sit on the single graph K26.
  2. Every colour class of a counterexample is pinned down. In any balanced colouring of K26, each of the five colour classes must have no six mutually joined vertices and no six mutually unjoined ones. Two lines of counting, and it kills every witness built by partitioning.
  3. The obvious counting attack is sharp, and still fails. It would decide the problem if a certain extremal number stayed below a threshold. At three colours it misses by exactly one edge (31 against 30). At five colours it misses by at least five (265 against 260). Curiously it is exactly tight at two colours, which is the one case where a counterexample really does exist.
  4. The affine construction cannot be pushed to twenty-six. Fifty pairs in the K25 colouring are free to be recoloured. No choice of those fifty, together with any colouring of a twenty-sixth point's edges, is balanced: a 375-variable refutation with a 1,160-line proof, checked by an independent verifier.
  5. No symmetric counterexample exists. At two colours the counterexample is a perfect pentagon. At five colours, all 3,198 candidate symmetric colourings fail, exhaustively. Any counterexample at K26 would have to be a lopsided object with no symmetry to help find it.
  6. And a reason nobody has just computed the answer. The direct search is pigeonhole-hard: even the already-proved three-colour case, at 135 variables, defeats four modern solvers unaided.

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.

AbstractSummary of results

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.

Section 1Setting, and two elementary facts

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.

Lemma 1 · Turán floor PROVED

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.

Fact A · no monochromatic Kr+1 PROVED

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.

Corollary A1 · the structured sector is empty PROVED

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.

Section 2Codes give balanced colourings

Lemma 2 · codes ⇒ balanced colourings PROVED

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.

Theorem 3 · T(r) ≥ r² for prime powers PROVED CERTIFIED WITNESSES

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).

Section 3What a K₂₆ witness must look like

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.

Section 4The counting barrier, sharp but never binding

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.

necessary for existence
E*(r²+1, r+1) ≥ (r−1)/r · C(r²+1, 2)
thresholds: 5 at r = 2, 30 at r = 3, 102 at r = 4, 260 at r = 5

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.

The counting barrier binds only where the conjecture is false. In the margin view the zero line is the counting threshold (r−1)/r·C(r²+1,2), and each bar is how far the extremal number E*(r²+1,r+1) clears it; the light tick above each bar is the Turán ceiling ex(r²+1;Kr+1), which no colour class complement can exceed. The margin is exactly zero at r = 2, the one case where a balanced colouring of Kr²+1 genuinely exists, and strictly positive everywhere the conjecture is believed. Bars at r = 4 and r = 5 are lower bounds, drawn hollow above the certified value, because the exact numbers are not pinned. Verify the witnesses re-runs the clique and independence tests on the committed extremal graphs, live, from the edge lists embedded in this page.
quantityvaluethresholdmarginstatus
E*(5,3)= 5 (C₅, classical)50anchor: met with equality, and realized
E*(10,4)= 3130+1CERTIFIED witness at 31, UNSAT at 32 in 4.6 s
E*(17,5)≥ 104102≥ +2CERTIFIED lower bound; ≤ 108 trivially
E*(26,6)≥ 265260≥ +5CERTIFIED lower bound; ≤ 269
max circulant on Z₂₆, no K₆ or I₆221 edges260−39CERTIFIED 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].

Proposition 4 · rigidity, refuted as stated

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.

Section 5Two certified exclusions at K₂₆

Lemma 5 · the affine family does not extend CERTIFIED (DRUP)

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.

Lemma 6 · profile arithmetic PROVED

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)}.

Theorem 7 · no dihedral witness CERTIFIED

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.

3,198 candidates, none survives
Every symmetric candidate dies, and you can watch it happen. The 26 vertices are the elements of the dihedral group D13 placed on a circle. Drawn is one candidate colour class, a union of Cayley classes with exactly 65 edges as Lemma 6 requires. The six ringed vertices are an independent set found in it, which is what disqualifies it: a balanced colouring needs every class to have independence number at most 5. Run the exhaustion rebuilds all 3,198 candidates in the browser and searches each for such a six-set. It is a live recomputation of Theorem 7, not a replay of a stored result. The contrast worth holding onto: at r = 2 the counterexample C₅ is a circulant, so the symmetric route is exactly the one that works two colours down.

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.

Section 6Why nobody has simply computed the answer

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.

instancewindowoutcome
K₁₀, r = 3, symmetry-broken—UNSAT in 3.1 s, the r = 3 theorem reproduced
K₁₇, r = 4, broken + cardinality3 h and 70 minunknown, even the proved r = 4 case resists at this scale
K₂₆, r = 5, broken + cardinality3 hunknown, the open case is beyond a four-core day by direct SAT
E*(17,5) ≥ 106 and ≥ 10820 min eachunknown, leaving the bracket [104, 107]
E*(26,6) ≥ 266, 267, 26960 to 90 min eachunknown, 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.

Section 7Open threads

  1. The K26 decision itself. The next tools, in order: verified symmetry breaking at scale (VeriPB-style), cube-and-conquer over colour-degree or K₆-pattern cubes on the broken and cardinality-strengthened formula, or an interaction lemma over the extremal catalogue.
  2. Pin the extremal numbers. E*(17,5) ∈ [104, 107] and E*(26,6) ∈ [265, 269]. Either endpoint is a new certified extremal value regardless of what happens to the conjecture.
  3. Read the two papers. Erdős–Gyárfás 1999 and Füredi–Ramamurthi 2002 were both unreadable from the sandbox this session ran in. Every secondary mark below has to be resolved before any external claim, and the construction and the code correspondence may well be theirs.
  4. Redo the rigidity analysis with classes constrained to [325 − E*, 105] once E*(26,6) is pinned, and check whether near-extremal (6,6)-graphs on 26 vertices are few enough to enumerate.