Graph colouring · discrete geometry
Take a shape cut into triangles, with no gaps and no overlaps, drawn flat on the page. Now paint each corner either red or blue. The one rule: no triangle may end up all one colour. Every triangle has to see both.
That is easy enough to do. The interesting question is whether you can do it fairly. If there are eleven corners you cannot split them evenly, but you would like to come as close as you can: six red and five blue, say, rather than nine and two. The discrepancy of a triangulation is the smallest gap between the two colour counts you can achieve while still giving every triangle both colours.
Basti and Cremaschi proved last month that the gap is never worse than a simple formula in the number of corners, and that a sharper formula also holds, except that their sharper proof breaks down for one family of sizes: 11, 17, 23, 29, 35 and so on, six apart. They left that family open and checked the smallest case, 11, by hand. Below is that smallest case. Try to colour it fairly.
What is not here: the residue class itself, for n ≥ 35. It stays open, and section 6 says exactly where the argument gives out.
A red–blue vertex colouring of a plane triangulation T is polychromatic if every face sees both colours; disc(T) is the least ||R| − |B|| over such colourings. Basti and Cremaschi (arXiv:2608.21585, 21 August 2026) prove disc(T) ≤ n − 2⌈n/3⌉ for all n (the Asayama–Matsumoto conjecture, via the balanced four-colour theorem of Kawarabayashi–Yoneda–Yoneda) and the sharper disc(T) ≤ U(n) := n − 2⌈(n+2)/3⌉ for n ≥ 6, n ≢ 5 (mod 6). They state that the class n ≡ 5 (mod 6), where U(6m+5) = 2m−1 against the universal 2m+1, remains open, and verify U(11) = 1 by exhaustive computation.
We prove a structure theorem for a hypothetical counterexample (Theorem 2): it must carry a proper 4-colouring with class sizes (3m+2, m+1, m+1, m+1) whose big class V1 is fully mixed, contains at least 2m+3 vertices of degree 3 and between 3 and m−1 vertices of degree ≥ 5 (none of degree 4), with every other vertex on a face avoiding V1. When the big class has at most two vertices of degree ≥ 5 the bound is proved (Theorem 3), which settles n = 11, 17, 23 and forces any counterexample to n ≥ 29. Independently, the structure theorem turns those orders into finite checks: the full census at n = 17 and a structural enumeration at n = 23 and n = 29, all certified.
| Result | Label | Scope |
|---|---|---|
| Structure theorem for a counterexample (Thm 2) | Proved | All n ≡ 5 (mod 6) |
| Refined bound when the big class has ≤ 2 high-degree vertices (Thm 3) | Proved | All n ≡ 5 (mod 6); hence n = 11, 17, 23 |
| Exact disc distribution, 13 ≤ n ≤ 17 (Thm 4) | Certified | Full census, 129,664,753 at n = 17 |
| disc(T) ≤ 5 = U(23) for all T on 23 vertices (Thm 5) | Certified | Via the structure theorem, not a census |
| disc(T) ≤ 7 = U(29) for all T on 29 vertices (Thm 6) | Certified | Via the structure theorem; ~8 core-hours |
| The n = 35 blocked configuration exists and has disc 1 | Certified (400 instances) / Numerical (in general) | SAT-built sample, not the full solution set |
| The residue class for n ≥ 35 | Open. Not settled here. | |
Write n = 6m+5. "The bound" means disc(T) ≤ 2m−1, equivalently: a polychromatic colouring exists whose smaller class has at least 2m+3 vertices. For v ∈ V1 the link Cv is the cycle of neighbours of v in rotation order; a colour pair occurs on Cv if some edge of the link has ends of those two colours. A face is V1-free if it contains no vertex of V1.
Let c be a proper 4-colouring of T with class sizes a ≥ b ≥ c ≥ d and a ≤ 3m+2. Then the bound holds unless (a,b,c,d) = (3m+2, m+1, m+1, m+1).
Since the balanced four-colour theorem [KYY, Corollary 17] supplies a proper 4-colouring with every class at most ⌊(n−1)/2⌋ = 3m+2: if disc(T) ≥ 2m+1 then T has a proper 4-colouring with class sizes exactly (3m+2, m+1, m+1, m+1).
Proof. Every face uses three distinct colours, so merging two classes into red and the other two into blue is polychromatic; it suffices to find two classes whose sizes sum to some s ∈ [2m+3, 4m+2]. Put r = a+d, s = b+c = n−r. As in [BC, proof of Thm 2.2], r ≥ b, c gives n ≤ 3r, and d ≤ (n−a)/3 gives r < 2n/3; so r, s ≥ ⌈n/3⌉ = 2m+2. The two boundary cases r = 2m+2 and s = 2m+2 are handled directly. ∎
Used as a black box: the balanced four-colour theorem of Kawarabayashi, Yoneda and Yoneda (arXiv:2607.13025, Corollary 17, checked in the HTML version on 4 September 2026). Everything downstream depends on it.
Two "flip" lemmas do the work. Lemma 2 says that if some v ∈ V1 has a link on which some colour pair occurs only once, the bound holds. Lemma 3 says that if some w ∈ W = V2 ∪ V3 ∪ V4 lies on no V1-free face, the bound holds. Counting the V1-free faces (Lemma 4) then pins the degree sequence, and Lemma 5 identifies G = T − V1 as a 2-connected plane graph on 3m+3 vertices, properly 3-coloured by V2, V3, V4.
If n = 6m+5 and disc(T) ≥ 2m+1, then T carries a proper 4-colouring with classes (3m+2, m+1, m+1, m+1) such that: (i) the big class V1 is fully mixed, every link showing all three colour pairs, so no vertex of V1 has degree 4; (ii) V1 has at least 2m+3 vertices of degree 3 and between 3 and m−1 of degree ≥ 5; (iii) every vertex of W lies on a V1-free face; (iv) G = T − V1 is 2-connected, plane, properly 3-coloured, on 3m+3 vertices; (v) no vertex has more than 2m+1 degree-3 neighbours in V1; and (vi) every single flip is blocked.
Concretely: a counterexample is a three-coloured plane graph G on half the vertices, with a set of its triangular faces left empty, and the remaining faces each stellated by one vertex of the independent big class. The figure in the plain-language section is exactly that construction at m = 1: G is the octahedron, three faces stay empty and cover all six vertices, and the other five are stellated.
Clause (ii) is the one that closes the small cases. A counterexample on 6m+5 vertices has at most m−1 high-degree vertices in the big class, so for m ≤ 3, that is n ≤ 23, there are at most two of them.
If T has a proper 4-colouring with classes (3m+2, m+1, m+1, m+1) in which at most two vertices of the big class have degree ≥ 5, then disc(T) ≤ 2m−1. Proved
Corollary. The refined bound disc(T) ≤ U(n) holds for every plane triangulation on n = 11, 17 and 23 vertices, the first three orders of the open residue class, and any counterexample has n ≥ 29.
The ingredients are the two recolouring lemmas above, a dominant-vertex lemma (Lemma 6), a single-flip lemma (Lemma 7) that recolours one class F together with a chosen part of the links, and an Euler-formula count (Lemma 8) on the subgraph induced by the high-degree links. With h ≤ 2 high-degree vertices, that count always finds an outside vertex with two degree-3 neighbours, and the flip goes through.
At h = 3 it does not, and section 6 shows the failure is real rather than an artefact of a lazy argument.
All computations use plantri 5.5 (Brinkmann–McKay) for generation and exact backtracking over colourings with monochromatic-face pruning. No floating point anywhere. Positive controls: the program reproduces [BC, Table 2] for 4 ≤ n ≤ 12 exactly, agrees with an independent brute-force Python implementation over all 2n−1 masks for n ≤ 11, and the generated counts equal OEIS A000109 at every order.
| n | triangulations (A000109) | disc 0 | disc 1 | disc 2 | disc 3 | disc 4 | U(n) |
|---|---|---|---|---|---|---|---|
| 13 | 49,566 | – | 49,562 | – | 4 | – | 3 |
| 14 | 339,722 | 339,300 | – | 422 | – | – | 2 |
| 15 | 2,406,841 | – | 2,406,752 | – | 89 | – | 3 |
| 16 | 17,490,241 | 17,481,631 | – | 8,596 | – | 14 | 4 |
| 17 | 129,664,753 | – | 129,662,101 | – | 2,652 | – | 3 |
Certified — 15 minutes for n = 17 on one core, run in the four residue-class parts of plantri's res/mod splitting (258 + 247 + 193 + 208 s). The 2,652 extremal triangulations at n = 17 are committed as certificates in data/n17_disc3.txt, and the extremal ones at orders 13, 15 and 16 likewise.
Every triangulation on 23 vertices satisfies disc(T) ≤ 5 = U(23). Certified
Of the 109,507,132 two-connected plane graphs on 12 vertices with 25 to 30 edges and faces of length at most 8, 1,848,652 pass the face filter (7,595 with no non-triangular face, 307,423 with one, 1,533,634 with two); they admit 11,678 equitable proper 3-colourings up to renaming; these give 998,162 choices of empty triangles covering every vertex, of which 948,057 have every occupied boundary fully mixed. Every one of the resulting 23-vertex triangulations has disc(T) = 1. None is a counterexample and none even reaches discrepancy 3. 277 s on one core.
The roughly 6·1010 triangulations of that order are far out of reach of a census; the structure theorem is what makes the check finite. That is also the caveat: this is a certification through the structure theorem, so it rests on Lemmas 1 to 5 and on plantri generating all 2-connected plane graphs with the stated parameters, not on an independent enumeration of the triangulations themselves.
Every triangulation on 29 vertices satisfies disc(T) ≤ 7 = U(29). Certified
By Theorem 3 a counterexample here would have exactly three high-degree big-class vertices, so T′ = T − D is one of the 977,526,957 triangulations on 18 vertices carrying three pairwise non-adjacent vertices of degrees (5,5,5) or (5,5,6). Processing all of them in four parts gave 4,151,483,419 admissible independent triples, 12,828,786 equitable 3-colourings, 62,588,172 choices of empty triangles covering every vertex, and 60,070,002 of those with every link fully mixed. Every one of the resulting 29-vertex triangulations has disc(T) = 1.
| Part | T′ read | Candidates | Fully mixed | Without safe flip | Wall (s) |
|---|---|---|---|---|---|
| 0 | 244,448,771 | 15,804,069 | 15,180,261 | 18,402 | 4,158 |
| 1 | 244,311,056 | 15,630,989 | 15,001,975 | 17,910 | 8,049 |
| 2 | 244,313,162 | 15,628,890 | 14,997,252 | 18,232 | 7,989 |
| 3 | 244,453,968 | 15,524,224 | 14,890,514 | 18,165 | 7,987 |
| total | 977,526,957 | 62,588,172 | 60,070,002 | 72,709 | 28,183 |
The last three parts were paused for an hour to give cores to another run, which is why their wall times are roughly double the first. Every candidate admits a single flip in the sense of Lemma 7, with zero exceptions; but 72,709 of them have no vertex off the three links with two degree-3 neighbours. So at n = 29 the situation of Lemma 8 genuinely fails, and it is Lemma 7's flips with the blocking analysis that carry the day. That is a signpost for whoever attacks the general case.
Together with Theorem 3: the refined bound holds for every n ≡ 5 (mod 6) with n ≤ 29, proved to 23 and certified at 29; a counterexample needs n ≥ 35 and at least three high-degree big-class vertices.
Clause (vi) of Theorem 2 can hold. If every vertex of W lies on the link of a high-degree vertex, and each such link is a hexagon coloured periodically 2,3,4,2,3,4, then every link vertex is of mixed type with a second edge of each of its two types elsewhere on the link, so no single flip in the sense of Lemma 7 survives. The smallest instance has m = 5, that is n = 35, with three pairwise disjoint hexagonal links covering the 18 vertices of W, using the entire degree budget Σ(deg − 3) = 9 = 2m−1.
Whether such a T exists is a small exact-cover problem on the 216 rainbow triples of W. A SAT model finds solutions; after discarding models whose vertex links are not single paths, the survivors are triangulations of the pair of pants, hence planar. Of the first 1,063 models, 400 are valid, and every one of the 400 resulting 35-vertex triangulations has disc(T) = 1 against the bound U(35) = 9.
So the obstruction is an artefact of the flip family, not a property of the triangulations: these T admit polychromatic colourings that no single flip produces, and a proof for h ≥ 3 needs a richer construction. The optimal colourings found are not class-based at all. In the first solution the three hexagons are coloured R,R,R,R,R,B / R,R,R,B,R,B / R,B,R,B,R,B, twelve red among the eighteen vertices of W, with the high-degree vertices B, B, R and ten of the fourteen degree-3 vertices blue.
Label discipline for this section. The existence and the discrepancy of those 400 triangulations are Certified. The statement "configurations of this type are always harmless" is Numerical: the 400 are a sample of the solution set, not all of it. And the residue class n ≡ 5 (mod 6) is not settled for n ≥ 35.
| Program | What it does | Cost |
|---|---|---|
disc.c | Exact disc(T) for plantri planar_code input; plantri n | ./disc -q -d 3 prints the histogram and dumps every triangulation with disc ≥ 3 | n = 17: 15 min over four parts |
census.sh | The n = 14…17 census driver (n = 17 in four res/mod parts) | see above |
struct_enum.c | The structural enumeration for n = 23 from 2-connected plane graphs on 12 vertices | 277 s, one core |
hstruct.c | The second parametrisation, used for n = 29 (hstruct 4 3) | 28,183 s total, four parts |
hexpants.py | The n = 35 blocked configuration, via pysat/CaDiCaL, then exact disc on each survivor | 400 valid models |
brute.py | Independent brute force over all 2n−1 masks, the positive control for n ≤ 11 | instant |
Run them from inside conjectures/triangulation-discrepancy/: the programs reference their data files by bare relative name.