Question 7.1, arXiv:2609.05259 · graph colouring
Take a network of dots joined by lines, where every dot has exactly three lines leaving it. Now colour everything, dots and lines alike, so that two things which touch never share a colour.
For these three-line networks, four colours are often enough. The interesting question is whether you can also use the four colours fairly: with each colour appearing about the same number of times, no colour used much more than another. Call a colouring that manages this an even one.
A paper posted on 4 September 2026 exhibited a 20-dot network that can be coloured with four colours but never evenly, and asked whether anything smaller does the same. Smaller networks are all catalogued, so this is a question a computer can settle, and the authors said as much. This note settles it: the answer is 16 dots, not 20, and there are exactly sixteen networks of that size that behave this way.
The figure is one of them. Press the search button and your own browser will work through every four-colouring it has and find that not one of them is even.
The paper's Question 7.1 asks whether every cubic graph of order below 20 that is four-total-colourable is also evenly four-total-colourable. A sweep of the catalogue answers it.
Everything below is the technical version. Section 3 is the census; the caveat that matters most is in section 5, namely that priority against an earlier dissertation has not been checked.
A total colouring of a graph colours vertices and edges so that adjacent vertices, adjacent edges, and incident vertex-edge pairs differ; a cubic graph is Type 1 when four colours suffice and Type 2 when five are needed. A total colouring is equitable when its colour classes, counted over all 5n/2 elements, differ in size by at most one, and χ''e is the least number of colours of an equitable total colouring. Adauto, de Figueiredo, Sasaki and Schneider (arXiv:2609.05259, 4 September 2026) exhibit a Type 1 cubic graph R of order 20 with χ''e = 5 and ask, as their Question 7.1, whether every Type 1 cubic graph of order below 20 admits an equitable 4-total colouring, remarking that the question is within reach of a systematic computation over the catalogue of connected cubic graphs of order at most 18.
It is. Sweeping that catalogue, all 45,982 connected cubic graphs of order at most 18, gives a negative answer: exactly 23 Type 1 cubic graphs of order below 20 have χ''e = 5, sixteen of order 16 and seven of order 18, so the minimum order is 16 and R is not extremal (Theorem 3.1, certified). Every Type 1 cubic graph of order at most 14 admits an equitable 4-total colouring. Every 4-total colouring of each order-16 exception has class configuration (11, 10, 10, 9), between 16 and 240 colourings per graph, all enumerated (Proposition 3.2, certified, SAT-free). A partial scan at order 20 finds 20 further examples, all with configuration (14, 12, 12, 12) like R. Priority against an earlier dissertation is not checked; see section 5.
Write N = 5n/2 for the number of elements of a cubic graph on n vertices, so that a 4-total colouring is a map from those N elements to four colours in which two elements that are adjacent or incident never agree. Equitable means every class has size ⌊N/4⌋ or ⌈N/4⌉. At n = 16 that is 40 elements and four classes of exactly 10; at n = 18 it is 45 elements and classes 12, 11, 11, 11.
The paper reduces the question to connected graphs, since colours can be permuted
independently in the components of a disconnected graph, and lists the catalogue of
connected cubic graphs as the natural object to sweep. Generation here is nauty 2.8.8
(geng -c -d3 -D3 n), whose counts 1, 2, 5, 19, 85, 509, 4060, 41301 for
n = 4, 6, …, 18 agree with OEIS A002851 and with the paper's total of 45,982.
Each graph becomes one SAT instance with a Boolean variable per element and colour: exactly one colour per element; for each edge uv and colour c, clauses forbidding u and v, the edge and u, and the edge and v from sharing c; and for each vertex, each pair of incident edges and each colour, a clause forbidding that pair. The equitable instance adds sequential counters bounding each class between ⌊N/4⌋ and ⌈N/4⌉. An optional symmetry break fixes one vertex to colour 0 and its three edges to colours 1, 2, 3, which is sound because those four elements are pairwise adjacent or incident and colour permutations preserve class sizes. Every refutation the result depends on was also produced without that prefix.
This page repeats a piece of that independently: the figure above re-derives, in the reader's browser and from the definition alone, both the colouring counts and the absence of an equitable one. For the first three order-16 exceptions the browser search returns 64, 240 and 80 colourings, matching the enumerator's numbers, and all sixteen counts were reproduced once more in Python on 20 September 2026 while this page was being written: 64, 240, 80, 40, 24, 96, 96, 32, 96, 64, 48, 28, 116, 28, 16, 96, every one of configuration (11, 10, 10, 9), none of them equitable. The same run enumerated the seven order-18 exceptions, which the session had not: their colourings number 64, 64, 20, 32, 20, 64, 32, and two of the seven also admit colourings of configuration (12, 12, 12, 9) alongside (12, 12, 11, 10), which answers question 3 of section 5 for all seven. That last observation comes from a single enumerator run during this page's preparation, not from the session's two-engine pipeline.
| n | connected cubic | Type 1 | Type 2 | Type 1 with an equitable 4-total colouring | Type 1 with χ''e = 5 |
|---|---|---|---|---|---|
| 4 | 1 | 0 | 1 | 0 | 0 |
| 6 | 2 | 1 | 1 | 1 | 0 |
| 8 | 5 | 4 | 1 | 4 | 0 |
| 10 | 19 | 9 | 10 | 9 | 0 |
| 12 | 85 | 60 | 25 | 60 | 0 |
| 14 | 509 | 461 | 48 | 461 | 0 |
| 16 | 4060 | 3833 | 227 | 3817 | 16 |
| 18 | 41301 | 39198 | 2103 | 39191 | 7 |
Question 7.1 has a negative answer. Exactly 23 connected Type 1 cubic graphs of order less than 20 admit no equitable 4-total colouring: 16 of order 16 and 7 of order 18, three of them bipartite. Every Type 1 cubic graph of order at most 14 admits one. The minimum order of a Type 1 cubic graph with χ''e = 5 is 16, and R, of order 20, is not of minimum order.
Each order-16 exception has between 16 and 240 4-total colourings up to colour permutation (64, 240, 80, 40, 24, 96, 96, 32, 96, 64, 48, 28, 116, 28, 16, 96 in the order of the figure), every one with class configuration (11, 10, 10, 9). This is consistent with the paper's Theorem 5.3, which allows only (10, 10, 10, 10) and (11, 10, 10, 9) at order 16. The order-18 exceptions have plain colourings of configuration (12, 12, 11, 10).
The sixteen order-16 exceptions are all non-bipartite, of girth 3 or 4, fourteen of them
2-connected and two with a bridge, with automorphism groups of order 2, 4, 8 or 16; not all
of them contain K2,3. Their graph6 strings are in
data/cx_n16.g6 and are the data behind the figure above.
At order 20 the sweep is incomplete: three of the ten geng residue classes,
161,130 of the 510,489 graphs, contain 20 further Type 1 graphs with χ''e = 5,
all with configuration (14, 12, 12, 12) like R, none isomorphic to R, whose own class was
not scanned. Each of those 20 verdicts is certified as above; the census is not.
R is given in the paper only as a figure. It was reconstructed here from that figure as
four K2,3 gadgets wired in a stated pattern, with graph6 string
S]o??KEH_???AB?J?@_?????@?W_?o?@o; the transcribed colouring from the figure is
a valid 4-total colouring with configuration (14, 12, 12, 12), and the equitable instance is
refuted with checked proofs of 1,314 and 8,198 lines. Two outer ports are clipped in the
printed figure and their colours are forced. Isomorphism between this
reconstruction and the graph of Dantas et al. was not verified: what is verified is
that the reconstructed graph has the properties the paper ascribes to R.