Catalogue · Proof · Exact checks · Issue #147
Status: Written proof for every even . It has been through one independent referee pass by a second model instance, which found no mathematical error; the justifications it asked for are included. The note is otherwise unrefereed. The finite checks cover and only.
Lean status: none. No Lean formalization is included.
Primary source: J. Mazák and F. Zrubák, Circular chromatic index of small graphs, arXiv:2603.08822, Conjecture 2.
Result
A circular -edge-colouring of a graph is a map such that whenever and share a vertex. The circular chromatic index is the least for which one exists; it satisfies .
Theorem. Let be even and let be the complete graph with one edge removed. Then .
This is Conjecture 2 of Mazák and Zrubák, who verified it by computer for . For the statement is false: .
Since , it suffices to exclude . By Guichard's theorem, whose proof is included, such a value would give a proper -edge-colouring whose digraph of consecutive colours is acyclic. The proof shows that the longest-path levels of that digraph order the edges linearly with rigid constraints. It then arranges the positions of each vertex in a table with columns and locates where each vertex changes rows. For two vertices of degree are forced to share two positions, although they are joined by exactly one edge. For this last step has nothing to compare, in accordance with the value .
Lemma 1 is Guichard's theorem and is not new. Guichard's paper is quoted through Zhu's survey and was not read directly. A literature search on 21 November 2026 found no proof of the conjecture.
Verification
Run from the repository root with Python 3.10 or later and no other dependencies:
python3 results/circular-index-complete-minus-edge/verify.pyPart A enumerates all 2160 proper 5-edge-colourings of , finds the 180 with acyclic digraph, and checks on each the statements of Lemmas 2, 3, 4 and 5(1). Part B searches exhaustively, up to automorphisms of the graph, for edge orderings with the properties of Lemma 3. There are 3 for , matching the 180 colourings of Part A, and none for . The script takes about 10 to 20 seconds.
The proof does not depend on any of the scripts. They check its statements on small cases. Our scripts cover directly; a run for was not completed. The computer check of Mazák and Zrubák covers . The theorem for general rests on the written proof.
Optional checks, not run by CI:
verify_sat.pyneedspython-sat. Run aspython3 results/circular-index-complete-minus-edge/verify_sat.py 4 6, it checks directly from the definition, without using any lemma, that has no proper 7-edge-colouring with acyclic digraph and that has one.review/contains the scripts of the referee pass, which share no code with the two above.d4_check.pychecks every statement from Lemma 2 to Lemma 7 on all 180 acyclic colourings of .sat_levels.py, run aspython3 results/circular-index-complete-minus-edge/review/sat_levels.py 4 6, is a second SAT check from the definition with a different encoding and needspython-sat.relaxed.py, run aspython3 results/circular-index-complete-minus-edge/review/relaxed.py 3 4 5, tests the implications of Lemmas 6 and 7 on relaxed configurations.arith.pychecks the arithmetic identities for .
Files
PROOF.md: statement, proof, the remark on , the verification summary and sources.verify.py: standard-library check of the lemmas for and of the ordering obstruction for .verify_sat.py: SAT check from the definition.review/: the referee pass's independent scripts.