Fabian Arevalo

Question 7.1, arXiv:2609.05259 · graph colouring

Sixteen vertices are enough to colour unevenly

A sweep of all 45,982 connected cubic graphs of order at most 18: exactly 23 are four-total-colourable but never equitably, 16 of order 16 and 7 of order 18, so the minimum order is 16 and not the 20 the question supposed.
8 September 2026 · hedge computation of a research session, about one core-hour · code, proofs and graph6 lists in the Matematica repository.

Start here — no maths required

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.

Order 1 / 16
One of the sixteen smallest exceptions. Vertices and edges carry one of four colours, drawn as four vertex marks and four line styles because this page has no palette. The colouring shown is computed in your browser by backtracking from the definition, not read from a file. The search button runs the exhaustive search with the even-size constraint imposed: for every one of these 23 graphs it finishes having found nothing, which is the result. Colour classes are counted over all 5n/2 elements, vertices and edges together.

What this note adds

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.

  1. No: the minimum order is 16. Among the 45,982 connected cubic graphs on at most 18 vertices, exactly 23 are four-total-colourable but never evenly: 16 on 16 vertices and 7 on 18 vertices, three of the latter bipartite. Below 16 vertices there is no exception at all.
  2. Each verdict carries a proof. Every "no even colouring" is a SAT refutation with a DRUP proof checked by an independent checker, with and without the symmetry-breaking prefix, and a SAT-free enumerator agrees on all 23.
  3. The exceptions are rigid. Every four-total colouring of each 16-vertex exception splits the 40 elements as 11, 10, 10, 9. Between 16 and 240 colourings each, all enumerated.
  4. A census on the way. The Type 1 and Type 2 split of every connected cubic graph up to 18 vertices, with all 2,416 Type 2 verdicts certified.

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.

AbstractSummary of results

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.

Section 1The question, and the encoding

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.

Section 2What is checked, and by what

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.

Section 3The census

nconnected cubicType 1Type 2Type 1 with an equitable 4-total colouringType 1 with χ''e = 5
410100
621110
854140
101991090
12856025600
14509461484610
1640603833227381716
1841301391982103391917
Where the exceptions appear. Every connected cubic graph up to 18 vertices, split by type. The catalogue grows by about a factor of ten per two vertices; the Type 2 graphs keep pace; the exceptions to equitability appear only in the last two rows, 16 of them at order 16 and 7 at order 18, and a zero is drawn as a tick on the baseline rather than dropped from the log axis. All three series are counts from the sweep, not a model.
Theorem 3.1 · certified

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.

Proposition 3.2 · certified, SAT-free

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.

Section 4What R is here, and what it 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.

Section 5Priority, and what is left

  1. Priority is unchecked. An earlier M.Sc. dissertation by Adauto (2022) and work by Stemock were not accessible from the machine that ran this. The paper states that orders at most 18 had not been checked, which is why the sweep was worth running, but no claim of novelty here has been verified against those two sources. The right next step is to check them and then report the 23 graphs to the authors.
  2. Finish order 20. Seven residue classes remain, roughly 1.5 hours on one core at the measured rate, which would give the full list at order 20 including R.
  3. Do the order-18 exceptions admit (12, 12, 12, 9) colourings? The session did not examine this; the re-verification run described in section 2 says two of the seven do and five do not, on one enumerator. Worth a second engine before it is relied on.
  4. A structural reason. The 23 graphs share features, bridges and K2,3 gadgets, that the paper's section 5 handles for R; a characterisation in that spirit would explain rather than exhibit.