Status: text proof, not formalised. It has been through one independent referee pass (a second model instance, report summarised under Verification). The finite checks in verify.py, verify_sat.py and review/ agree with it.
Statement
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 . [MZ, Section 1; Zhu01]
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 [MZ], who verified it by computer for . For the statement is false: [MZ]. The proof below shows where is used (last step).
Throughout, with , , and
The vertices are called special (degree ), the others normal (degree ). Any two normal vertices are adjacent. Since is odd, a matching has at most edges, so , and . Hence and . The task is to exclude .
Step 1. Acyclic colourings
For a proper colouring of a graph let be the digraph on with an arc whenever and .
Lemma 1 (Guichard [Gui93]; see [Zhu01, Theorem 3.1]). If , then has a proper colouring for which has no directed cycle.
Proof (included for completeness). Since , there is a circular -colouring with . Here : otherwise would be a proper colouring with the colours . Put . Adjacent vertices have , so is proper. For an arc with we get , hence . For an arc with , we get . A directed cycle passes through the colours cyclically, so it has arcs of which are of the second kind. Summing along the cycle gives , a contradiction. ∎
Apply this to the line graph of . From now on assume, for a contradiction, that is a proper edge-colouring whose digraph is acyclic. The vertices of are the edges of , and means that share a vertex and . Write .
Step 2. Colour classes, the source and the sink
Lemma 2. After adding a constant to all colours:
- and for . So misses exactly three vertices, forming a set , and each other class misses exactly one vertex.
- has exactly one source and exactly one sink . Moreover , , and both edges have both ends in .
Proof. (1) Each class is a matching, so has at most edges, and . Adding a constant to all colours does not change . (2) An edge of colour is a source exactly when no edge at or has colour , that is when misses both and . Then and . Two such edges would be disjoint edges of inside the three-element set . So there is at most one source, and in the same way at most one sink, of colour inside . A finite acyclic digraph has a source and a sink. ∎
Step 3. The longest-path levels form a linear order
For an edge let be the number of arcs of a longest directed path of ending at .
Lemma 3. is a bijection from onto , and . The edges with and share a vertex. Finally:
(P) if share a vertex and , then .
Proof. A longest path ending at starts at a source (otherwise it could be extended backwards, and in an acyclic digraph the extended walk is again a path), hence at , and colours increase by one along arcs. So . Write with ; thus for the colours . For an arc we have , which gives
For let be the set of edges of colour sharing a vertex with an edge of . We claim:
- (E1) for , , and for ;
- (E2) for .
Indeed, the edges of cover vertices. In (E1) the class misses only one vertex. In (E2) the class misses the three vertices of , but two of them are the ends of and are not covered by . So in both cases at least of the covered vertices lie on an edge of the next class, and these edges number at least .
Let be the number of edges with . The sets are mapped by into the corresponding set of the next class, and into the set with when . With (E1), (E2):
Hence . On the other hand every level between and contains an edge (the predecessor on a longest path has level one less), and level consists of the edges of colour 1 with . So whenever . Therefore all the inequalities above are equalities for these . Let be the least integer with , so that no edge has . Starting from and going down by one at each step we reach , so . For we get for and , and for all . So for each colour and each there is exactly one edge of colour with , and for colour 0 exactly one for each and none with . These are edges on the levels , one on each.
The edge of level has an in-neighbour of level , so the two share a vertex. For (P): would give two edges of the same colour at a vertex. If then , so is an arc and . ∎
Let be the edge with . We say that a vertex is at position if . Every position holds exactly two vertices. Since each edge of has exactly one position:
(M) two normal vertices have exactly one common position; and have none; a normal and a special vertex have exactly one.
Step 4. Runs
Let be the positions of a vertex . A run of is a maximal set of consecutive integers among them, and is the number of runs.
Lemma 4.
- For a normal vertex, for all .
- For exactly one vertex is at both positions and . Hence .
- There is exactly one vertex in . It is normal and . Every other normal vertex has , and its first position and last position satisfy , so . For every normal vertex, a run ending at that is not its last run is followed by a run starting at ; equivalently, a run starting at that is not its first run is preceded by a run ending at . All runs of and of have length one.
Proof. (1) Let be the colour missing at and let be the edge at of colour , . Then is an arc, so and the difference is .
By Lemma 3, and are distinct edges sharing a vertex. Counting pairs (vertex, position) gives and .
Let be normal and write . By (1), , where is the sum of . Steps inside a run contribute 0 and steps between runs at least 1, so , with equality exactly when all steps between runs equal . Since , we get for an integer , and because . Moreover
Here only if , which holds for at most one vertex. Let be the number of normal vertices with . Special vertices have . With (2):
So and equality holds everywhere: one normal vertex has and ; every other normal has , that is , and ; all steps between runs of normal vertices equal ; and , which is the number of edges at and at . ∎
For let be the vertex of not in , and for let be the vertex of not in . By Lemma 4(3), a special vertex at position equals and whenever these are defined. In particular:
(C) the vertex common to and is always normal; and if is a position of a special vertex and is the normal vertex of , then (if ) and (if ).
Step 5. The table with columns
Write every position as with row and column . Since , the columns (the left half) have the rows and the columns (the right half) have the rows . A position is special if it holds or .
Lemma 5.
- The special positions are exactly the positions in four columns with in .
- Let , so . Every column is the first position of exactly one normal vertex , and these are all the normal vertices other than .
- Let be normal with first position , and put if and if . There are integers such that the positions of are exactly
and is at both and exactly for , . If the column of is special, then .
Proof. We first prove the description of the positions in (3), then (1) except for the form of the right special columns, then (2) together with that form, and finally the last sentence of (3).
Positions in (3). By Lemma 4 the steps of are 1 or , and there are steps of the second kind. Let count the steps of the first kind and those of the second kind made so far. This gives the description; the final value of is , which is for and for .
(1), closure and count. Let be special, holding the special vertex , and let . Put . If were normal, its run starting at would not be its first, since first positions are at most . So its previous run ends at (Lemma 4(3)), hence , a contradiction. So is special. Symmetrically, if then is special: a normal would not be in its last run, since last positions are at least , and its next run would start at , giving . Hence the set of special positions is a union of whole columns. There are special positions, a left column has positions and a right column . If there are left and right special columns, then , that is . With and the only solution is : the right side lies between and and is divisible by , so it is (giving , ) or (giving , ), or, for only, (giving , ).
(2), and the form of the special columns. The first positions of the normal vertices other than lie in (Lemma 4). They are distinct, because for only can have first position , and position 0 holds and one other vertex. None of them is special: at a special position the starting vertex is special, and a special position 0 holds and a special vertex. As exactly columns are not special, each of them is the first position of exactly one such vertex. The last position of is . It is not special: otherwise it is not (because would then consist of and the normal vertex ), and then (C) puts at the next position as well. So the set of non-special columns is closed under adding modulo , which gives the form of the special columns in (1) and of .
Last sentence of (3). Let the column of (that is, ) be special. By (1) the position is then special. If , then is not at the next position, against (C). ∎
For we call unwrapped and wrapped. By Lemma 5(3):
- has its positions in the columns ;
- in the columns , and its position is in row ;
- in the columns (row ) and (row ).
In every column that a normal vertex visits, its rows form an interval. Each of these intervals begins in the row where the previous one ends, except that for a wrapped vertex the interval in column 0 begins one row below the end of its interval in column (position is followed by position ). We call the number of junctions of at . Thus for , and junctions occur only in non-special columns.
Rows at a boundary. For a column and a normal vertex that is at positions and for some , this is unique by Lemma 5(3); call it . By Lemma 5(3) the vertices for which it exists are , the with and the with (). These are vertices. For each of them the value lies in , because the left column has exactly these rows. Conversely, each of the positions , , is at most , so it has exactly one vertex in common with the next position (Lemma 4(2)); this vertex is normal by (C), hence it is one of the vertices listed, with equal to . So:
(B) for , is a bijection from onto .
In the same way the rows in which the () pass from column to column are distinct and at most ; call them . And the rows in which the arrive in column 0 are distinct and at least 1; call them . Put also , , and . These conventions do not clash with the values defined before: the list in (B) for the column does not contain , the list for the column does not contain , and occurs neither among the vertices passing from column to column nor among those arriving in column 0 from column . With these conventions, for every normal vertex and every left column that it visits:
(R) the set of rows of in column is the interval .
(For in its first column this says that it starts in row 0; for in its last column , that it ends in row , the row of its last position; for , that it starts at position 0 and ends at .) A consequence:
(O) if both visit the left column and while , then , so and have a common position in column .
Step 6. The vertex separates unwrapped from wrapped vertices
Let , with .
Lemma 6. Let and . If then . If then . Consequently , the with occupy the rows at this boundary, and the with occupy the rows .
Proof. By (B), distinct vertices have distinct values of , so in the comparisons below "not greater" means "smaller" and conversely. Suppose for some and take minimal. Then and have a common position in column : for because , and for by (O). If for some , the least such gives, by (O), a common position in column . Otherwise , and then because ; this is a common position in column . Both cases contradict (M).
Suppose for some and take maximal. Then there is a common position in column : for because , and otherwise by (O). If for some , the largest such gives a common position in column . Otherwise and , a common position in column . Again (M) is contradicted.
The last sentence follows from (B). ∎
So for every left column : one row if , and the two rows if is the -th element of .
Step 7. Where the other vertices have their junctions
Write .
Lemma 7. For :
- and ;
- has junctions at , junctions at , and no others. So it occupies the rows of column , row of the columns , and the rows of column .
Proof. (1) By (M), and have exactly one common position, in a left column . By Lemma 6 and the bound , the rows of in column are at most . So a common row exists only if for some and . For a given at most one has this property, by (B) (and by the distinctness of the when ). So is an injective map of into itself with , hence the identity. Thus .
Likewise and have exactly one common position, in a left column , and the rows of in column are at least . (For this is Lemma 6 at the column ; for it is the bound of Step 5.) A common row exists only if with and . For a given at most one qualifies, by (B) at the column (and by the distinctness of the arrival rows when ). So is injective with , hence the identity, and .
- The vertices and visit the columns and respectively, so their common columns are and . By (1) they have no common row in column , so by (M) they have one in column . There has the rows and the rows . By (1), and , so and , that is
A common row forces equality in both places. Then all junctions of are at and . ∎
Step 8. The contradiction
Since , the set has at least two elements . By Lemma 7(2):
- is in row 0 of every column and in the rows of column ;
- is in the rows of column , in row 1 of the columns , and in the rows of column .
Now . So both vertices are at the position in row 0 and column , and both are at the position in row 1 and column (note ). These are two different positions, which contradicts (M). Hence no proper -edge-colouring of has an acyclic digraph, and by Lemma 1, . ∎
Remark (). For the set has one element and Step 8 has nothing to compare. Steps 2 to 4 remain valid for , and acyclic colourings exist (for the counting argument in Lemma 5(1) is not conclusive, but verify.py confirms its statement on all acyclic colourings). With vertices , the order
with colours is one. By the converse direction of Guichard's theorem [Zhu01, Theorem 3.1], which we do not prove here, an acyclic colouring gives , in accordance with the value of [MZ].
What is new
The Theorem, for all even . Mazák and Zrubák state it as a conjecture and report a computer verification for [MZ, Conjecture 2 and the sentence after it]. Lemma 1 is Guichard's theorem and is not new. We found no proof of the conjecture in the literature (search of 21 November 2026).
Verification
The proof does not depend on any of the scripts. They check its statements on small cases.
verify.py(standard library;python3 verify.pytakes about 10 seconds). Part 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 (consecutive edges share a vertex, and (P)): there are 3 for (and , with 5 rotations of the colours and 12 automorphisms), and none for .verify_sat.py(needspython-sat) checks directly from the definition, without using any lemma, that has no proper 7-edge-colouring with acyclic digraph (38 s), and that has one. Acyclicity is encoded by a transitive order on the edges.review/contains the scripts of the referee pass, which share no code with the two above:d4_check.py: on all 180 acyclic colourings of , every statement from Lemma 2 to Lemma 7, including (E1), (E2), (M), (C), (B), (R).sat_levels.py 4 6: a second SAT check from the definition, with acyclicity encoded by an integer potential; is unsatisfiable (224 s).relaxed.py 3 4 5: enumerates, for , all configurations that satisfy the conclusions of Lemmas 4 and 5 for the normal vertices, without imposing (M). There are 3, 66 and 13380. On all of them (B) holds, the conclusions of Lemmas 6 and 7 follow from their hypotheses, and for none has every pair of normal vertices meeting exactly once.arith.py: the identities for and the counting in Lemma 5(1) for .
The referee pass found no mathematical error. It asked for the justifications that are now in the proofs of Lemma 1, Lemma 5 (order of the argument), (B), Lemma 6 (distinctness) and Lemma 7(1) (the case ), and for the correction of one sentence in Step 5 that was not used.
The computer check of [MZ] covers ; our scripts cover only directly (we did not complete a run for ).
Sources
- [MZ] J. Mazák and F. Zrubák, Circular chromatic index of small graphs, arXiv:2603.08822 (March 2026). Conjecture 2; the value for ; definitions.
- [Gui93] D. R. Guichard, Acyclic graph coloring and the complexity of the star chromatic number, J. Graph Theory 17 (1993), 129–134. Lemma 1. † Quoted through [Zhu01].
- [Zhu01] X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001), 371–410. Basic facts on and the statement of Guichard's theorem.
† marks a source we did not read directly.