Fabian Arevalo

Graph colouring · discrete geometry

The open residue class of the triangulation discrepancy bound, at its first four orders

A structure theorem for any counterexample, a proof of the refined bound at n = 11, 17, 23, a certification at n = 29, and the exact discrepancy table extended from n ≤ 12 to n ≤ 17.
September 4, 2026 · session of the Matematica research log · code, certificates and note in conjectures/triangulation-discrepancy/

Start here — no maths required

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.

An eleven-corner triangulation, the smallest size in the open family. Click any corner to switch it between red (filled) and blue (hollow). Triangles that have gone all one colour are shaded; the tally underneath counts them and reports the gap between the two colour counts. Everything here is computed live: the "search all 2048" button really does enumerate every colouring of the eleven corners and report the smallest gap achievable, which is 1. This particular triangulation is not decorative, it is built by the construction of section 2: an octahedron with five of its eight faces stellated, which is exactly the shape any counterexample would have to take.

What this note adds

  1. A shape theorem for any counterexample. If the sharper bound ever fails, the triangulation has to look one very specific way: half its corners form an independent set sitting inside the faces of a three-coloured graph on the other half, most of them touching exactly three triangles, and every simple repair move has to be blocked. Proved.
  2. The sharper bound, proved, at the first three sizes of the open family: 11, 17 and 23. More generally it is proved whenever the big colour class contains at most two corners of degree five or more. Since a counterexample on 6m+5 corners can have at most m−1 of those, that settles everything below 29.
  3. At size 29 it is certified rather than proved, by grinding through the one case the proof leaves open: all 977,526,957 triangulations on 18 corners, giving 60,070,002 candidate shapes, every one of discrepancy 1 against a bound of 7. About eight core-hours.
  4. The exact discrepancy table, extended. The paper published it to 12 corners. Here it runs to 17: all 129,664,753 triangulations on 17 corners have discrepancy at most 3, and exactly 2,652 of them hit it.
  5. The first shape the proof cannot handle exists, and is harmless. At 35 corners there are triangulations where every simple repair move is blocked. Four hundred of them were built with a SAT solver, and every one has discrepancy 1 against a bound of 9. So the obstruction is in the method, not in the triangulations.

What is not here: the residue class itself, for n ≥ 35. It stays open, and section 6 says exactly where the argument gives out.

AbstractSummary of results

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.

ResultLabelScope
Structure theorem for a counterexample (Thm 2)ProvedAll n ≡ 5 (mod 6)
Refined bound when the big class has ≤ 2 high-degree vertices (Thm 3)ProvedAll n ≡ 5 (mod 6); hence n = 11, 17, 23
Exact disc distribution, 13 ≤ n ≤ 17 (Thm 4)CertifiedFull census, 129,664,753 at n = 17
disc(T) ≤ 5 = U(23) for all T on 23 vertices (Thm 5)CertifiedVia the structure theorem, not a census
disc(T) ≤ 7 = U(29) for all T on 29 vertices (Thm 6)CertifiedVia the structure theorem; ~8 core-hours
The n = 35 blocked configuration exists and has disc 1Certified (400 instances) / Numerical (in general)SAT-built sample, not the full solution set
The residue class for n ≥ 35Open. Not settled here.

Section 1The setting, and where the class vector comes from

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.

Lemma 1 and its corollary

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.

Section 2What a counterexample would have to look like

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.

Theorem 2 — structure of a counterexample

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.

Section 3The proof when the big class has at most two high-degree vertices

Theorem 3

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.

Section 4The exact discrepancy table, to seventeen vertices

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.

ntriangulations (A000109)disc 0disc 1disc 2disc 3disc 4U(n)
1349,566–49,562–4–3
14339,722339,300–422––2
152,406,841–2,406,752–89–3
1617,490,24117,481,631–8,596–144
17129,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.

The two bounds and what actually happens. For each order n, the bars are the largest discrepancy attained by any triangulation on n vertices; the upper line is the universal bound n − 2⌈n/3⌉ and the lower one the refined bound U(n) = n − 2⌈(n+2)/3⌉, both computed live from the formulas. Filled bars are orders in the open residue class, n = 11 and 17. Orders 6 to 12 are the paper's own Table 2, reproduced here by an independent implementation; 13 to 17 are new. The sentence to take away: at every order the largest discrepancy that occurs is exactly the refined bound, including at the two orders where nobody had proved that it must be.
Extremal triangulations get rare fast. The fraction of all triangulations on n vertices that attain U(n), on a logarithmic scale. Measurement, exact counts from the census (and from [BC, Table 2] at n = 10 and 12). At n = 11 every triangulation attains the bound, because U(11) = 1 is forced by parity, so that order is shown separately rather than plotted as a fraction. From n = 13 on the fraction falls by roughly an order of magnitude per two vertices, which is why finding a counterexample by random search is hopeless and why the structure theorem was necessary.

Section 5Twenty-three and twenty-nine, through the structure theorem

Theorem 5 — n = 23

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.

Theorem 6 — n = 29

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.

PartT′ readCandidatesFully mixedWithout safe flipWall (s)
0244,448,77115,804,06915,180,26118,4024,158
1244,311,05615,630,98915,001,97517,9108,049
2244,313,16215,628,89014,997,25218,2327,989
3244,453,96815,524,22414,890,51418,1657,987
total977,526,95762,588,17260,070,00272,70928,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.

Section 6What remains open, and why

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.

Section 7Reproducing this

ProgramWhat it doesCost
disc.cExact disc(T) for plantri planar_code input; plantri n | ./disc -q -d 3 prints the histogram and dumps every triangulation with disc ≥ 3n = 17: 15 min over four parts
census.shThe n = 14…17 census driver (n = 17 in four res/mod parts)see above
struct_enum.cThe structural enumeration for n = 23 from 2-connected plane graphs on 12 vertices277 s, one core
hstruct.cThe second parametrisation, used for n = 29 (hstruct 4 3)28,183 s total, four parts
hexpants.pyThe n = 35 blocked configuration, via pysat/CaDiCaL, then exact disc on each survivor400 valid models
brute.pyIndependent brute force over all 2n−1 masks, the positive control for n ≤ 11instant

Run them from inside conjectures/triangulation-discrepancy/: the programs reference their data files by bare relative name.