Status: written proof with one independent model referee pass (written 2026-11-21). Theorems 1 and 2 and the regular C31/C33 examples of Section 7.2 now have complete Lean proofs, including degree, vertex connectivity, and the real circular chromatic index. Their 19-module closure passed strict source checks, an all-owned axiom audit, and stock-kernel replay; see the landing page and receipt. The nonregular examples, additional structural/insertion lemmas, and SAT exclusions remain outside that formalized scope. The Python checks remain verify.py and verify_part2.py; referee report and scripts are in review/.
0. Context
Mazák and Zrubák, Circular chromatic index of small graphs, arXiv:2603.08822v1 (submitted 9 March 2026), Section 8, contains the following (quoted from the arXiv HTML version through a fetch tool; see Sources):
- "It would also be interesting to know which denominators are possible in the upper half of the interval ."
- Problem 7. "Does there for every integer q > 2 exist an integer p and a (multi)graph G with ?"
- "Currently, for any , we don't even know if there is a single graph with maximum degree and ."
- Problem 6. "For which d does there exist a d-connected d-regular graph with circular chromatic index at least d + 1/2?" It is preceded by: 3-connected cubic graphs with have long been known (Lukoťka–Mazák), and "Theorem 9 proves the existence of a 4-connected 4-regular graph G with (an infinite family of them, actually)" — namely the circulants , (their Theorem 9: "There exist infinitely many 4-connected 4-regular graphs G with ").
The values in the open upper half that the paper lists have (e.g. Petersen, , , , , , , ).
1. Statement
Notation. For an odd and , the circulant is the Cayley graph of with connection set : vertex set , iff . The length of an edge is the unique with . is the matching number.
Circular edge-colourings. For real , a circular -edge-colouring is a map such that edges sharing a vertex get colours at circular distance ; is the infimum (in fact minimum) of such (this is the definition used by Mazák–Zrubák). For integers , a -edge-colouring is a map such that edges sharing a vertex get colours at circular distance in . The colour classes are .
Theorem 1. Let , and
Then is a simple -regular, -connected graph and
Theorem 2. The circulant is a simple 18-regular, 18-connected graph with .
Smallest cases of Theorem 1: (, ), (, ), (, ).
2. Proof
2.1 Two general lemmas on
Lemma 1 (lower bound). If has at least one edge, then .
Proof. (This is the classical bound , cf. Zhu's survey and Hackmann–Kemnitz, the reference [11] of Mazák–Zrubák; here is a direct argument.) Let be a circular -edge-colouring ( by definition). For let , a half-open circular arc of length 1 (the whole circle if ). Two colours in are at circular distance , so is a matching and . Each colour lies in for a set of of measure exactly 1, so
Hence for every admissible , and the same holds for the infimum.
Lemma 2 (upper bound and window form). (a) If has a -edge-colouring then . (b) A map is a -edge-colouring iff for every the window is a matching.
Proof. (a) satisfies for adjacent . (b) Two adjacent edges with colours at circular distance lie in a common window (the window starting at the "earlier" of the two colours along the shorter arc), and conversely two edges in a common window have colours at circular distance .
2.2 The graph
Let . For these numbers are distinct () and lie in ; as is odd, , so has distinct non-zero elements and is a simple -regular graph with
It is connected () and not complete ().
Every edge of is for a unique length , and for fixed the translates , , are pairwise distinct: with would force and , hence , impossible for odd . So the edges of length are exactly the translates of any one of them.
2.3 Upper bound: an explicit -edge-colouring
Define two sets of edges ("base classes"):
Vertex sets. , , . Hence the vertex sets of , are
(intervals of integers, all inside ). Each has elements and has edges, so , are matchings.
Lengths. In : has length ; has difference , i.e. lengths (all odd numbers in ). In : has length ; has difference , i.e. lengths (all even numbers in ). So the base edges have pairwise distinct lengths and their lengths are exactly .
Classes. Index classes by , writing with , (this is a bijection , and ):
By 2.2, for each the classes ( the parity class containing the base edge of length ) contain the distinct edges of length ; thus the classes partition , each edge lying in exactly one class ( confirms the count). Each class is a matching (a translate of ).
Colours. Since (), is a bijection of ; colour every edge of with . As , we have : colour is carried by class and colour by class .
Window condition. By Lemma 2(b) with , and since each class is a matching, we must show that for every the classes , , are pairwise vertex-disjoint; as ranges over all of it suffices that for all
(the pair is the first condition at ).
Reduction to translates, with : - is odd. If : , class . Condition: , i.e. (C1) . If : , class . Condition (C2) . - is even: , class . Condition . Since , this is , equivalently (translate by ) (C3) and (C4) .
Checks (all integers below are in unless reduced): - (C1) . : , , . Disjoint. - (C2) (as ). : , and misses , and . Disjoint. - (C3) versus . Disjoint. - (C4) versus (). Disjoint.
Hence is a -edge-colouring of and, by Lemma 2(a), .
(Remark: each window consists of three classes with vertices each, i.e. it is a matching of size covering all vertices but one. This is exactly the equality case of the averaging in Lemma 1.)
2.4 Lower bound and conclusion
is odd, so ; the edges , , have length and form a matching of size , so . By Lemma 1,
Together with 2.3, . (Of course also .)
2.5 Connectivity
Let be a connected, non-complete graph with vertex connectivity . For put and . If then separates from , so .
Definition. A fragment is a set with , and . An atom is a fragment of minimum cardinality; this cardinality is denoted . (Fragments exist: for a minimum separator and a component of , and , so .)
Two facts used below: (i) if is a fragment then so is , with and — indeed no vertex of is adjacent to , so , and lies outside , so ; in particular . (ii) If is an atom then .
Lemma 3 (Watkins 1970; Mader). Distinct atoms are disjoint.
Proof (included for completeness). Let be atoms with . Partition by the rows , , and the columns , , ; let and . A neighbour of a vertex of lies in , a neighbour of a vertex of in , and similarly for columns. Hence
and in each case the "opposite corner" ( for , for , …) lies outside . Put , ; then ; likewise and satisfy .
If : and lies outside , so and is a fragment; forces .
If , then . If , then lies outside , so , impossible; so . From we get , and from we get . Now and by (i), so ; likewise gives . Each of lies outside the other's closed neighbourhood, so , while . Hence , is a fragment contained in , so , contradicting .
Lemma 4 (atoms of Cayley graphs; cf. Hamidoune 1977). Let be a connected non-complete Cayley graph of a finite group (here , written additively). Then the atom containing exists, is unique, and is a subgroup of .
Proof. Automorphisms map fragments to fragments and atoms to atoms. Translations are automorphisms. If is any atom and , then is an atom containing ; by Lemma 3 it is the unique one, call it . For , is an atom containing , so . Thus for all , and is a subgroup.
(Lemma 3 says the atoms form a system of blocks of imprimitivity of when is vertex-transitive — Watkins' theorem; Lemma 4 is the special case of a regular subgroup.)
Proposition 5. for every .
Proof. Let be the atom containing ; by Lemma 4, for a divisor of , of index and order . is impossible ( would be empty). - If : the cosets of are , , and every . So every is with , , hence adjacent to : , , contradicting that is a fragment. - If : , and divides , which is odd and ; hence .
So is an atom and by (ii).
(Edge connectivity is then also , as .)
This completes the proof of Theorem 1.
2.6 Proof of Theorem 2 ()
, : nine distinct lengths in , so is simple, 18-regular, . By 2.2-type reasoning, the edges of each length form one translation orbit of size 25.
Colouring (found by search/cyc2.py: python3 search/cyc2.py 100 12,3). Base classes (each a matching of 3 edges):
with lengths , , — together exactly , each once. Vertex sets , , . For write , , , and put , coloured (). The 75 classes partition (each length occurs in exactly one , and its 25 translates are distinct).
, so a window of 4 consecutive colours is . With , , , the condition "class disjoint from class for and all " becomes for the nine triples :
Check: , , , , , , , , , and each is disjoint from the corresponding (first entry of the triple): e.g. , , , , and all other elements of the nine translates lie in , which no meets. So this is a -edge-colouring and . Lower bound: (matching ), .
Connectivity. The subgroups of are . For : (), so every non-zero coset is met by and, as in Proposition 5, it is not a fragment. Hence the atom at is and .
3. Consequences for the questions of Mazák–Zrubák
The remark "for any we don't even know a single graph". Answered for every with (Theorem 1, value ) and for (Theorem 2, value ). The graphs are simple, regular, and of connectivity . For with , , Theorems 1–2 give nothing; Section 7 (computer-certified, not a general proof) adds the non-regular cases and and the regular case , value .
Problem 6. Read literally ("at least ", upper end allowed), Problem 6 is trivially answered for every even by (which is -connected and has , as Mazák–Zrubák themselves note in Section 4; they also note that is 4-connected with ). The non-trivial reading, suggested by the context (the cited examples have exactly, and the paper is about values strictly below ), asks for . For that reading Theorems 1–2 give an affirmative answer for , with , strictly inside (Section 7.2 adds a second example, with ). The context also supports a third reading, exactly (the cited examples for have exactly this value). Theorems 1–2 do not answer that reading: our values are , , , never ; it remains open here for every . Known before (per the paper): . Open (as far as this note goes): odd and even with , . Note that for odd a -regular graph has even order, so the overfull mechanism used here (odd order) is unavailable.
Problem 7. Not answered. Our denominators are (all , ) and (); the paper already has (at ). What is new is that is realised with arbitrarily large by simple, regular, maximally connected graphs, and at . In addition (Section 7.2, computer-certified, checked by the referee), is 18-regular, 18-connected with : denominator 5 for a simple regular graph (the paper has only as , for multigraphs with ). This still says nothing about .
A general remark (elementary). If is -regular of odd order then Lemma 1 gives , which is as soon as ; and (Vizing). So dense odd-order regular graphs automatically have in the closed upper half; the whole difficulty is to show (e.g. has ). The constructions above do this by exhibiting a colouring meeting the fractional bound exactly ("perfect" colouring: every window of consecutive classes is a near-perfect matching).
4. What is new
- An explicit infinite family of simple -regular, -connected circulants with , one for every , ; plus one with , . According to Mazák–Zrubák (March 2026) no graph with and was known. We did not perform an exhaustive literature search beyond that paper and a few web searches (which found nothing more recent on this question).
- The proof method: "perfect" circular colourings in which every window of consecutive colour classes misses exactly one vertex, so that the trivial lower bound is attained; for circulants these can be sought with a cyclic ansatz (classes indexed by , translation-equivariant).
- Nothing new is claimed about atoms or connectivity; Lemmas 3–4 are classical and reproved only for completeness.
5. Verification
verify.py (standard library only; run python3 verify.py, about 0.3 s) checks, for : the circulant is simple and -regular; the classes partition the edge set (each edge exactly once); is a bijection of and ; every class is a matching; the colouring is a -colouring, checked both per vertex (cyclically sorted incident colours differ by ) and per window (every 3 consecutive classes are pairwise vertex-disjoint); the matching exists, so , and . Vertex connectivity is computed by its own max-flow routine (vertex splitting, BFS augmenting paths): for over all non-adjacent pairs and for over pairs (sufficient by vertex-transitivity). The same checks are made for Theorem 2 (-colouring, , over all pairs). Output ends with ALL CHECKS PASSED. The max-flow routine was cross-checked against networkx.node_connectivity on seven circulants (outside verify.py).
Referee pass. One independent model referee (report review/REVIEW.md) checked by hand: Lemmas 1–2; the classes, lengths and partition in 2.3; and the reduction to (C1)–(C4) and each of (C1)–(C4); ; Lemma 3 line by line, Lemma 4, Proposition 5 and the atom arguments for ; the nine translate conditions of Theorem 2; (C1)–(C4) for the Family B vertex sets; the Section 7 lemmas; the quotations from Mazák–Zrubák. Independent computations (own code, networkx for and , not importing ours): Theorem 1 colourings for ( by max-matching for ), for , for , ; all Part 2 certificates rebuilt with , , and ; exhaustive confirmation that the Family B base problem is unsolvable for and solvable for ; brute-force confirmation of UNSAT for cyclic (the other UNSAT claims of 7.4 were not re-checked); 60 random insertions (both forms) into Family B bases passed and 60 negative controls failed. No errors were found; the gaps it listed (mirror form, edge-disjointness for several insertions, wording in 7.1, the reading of Problem 6, mention of in Section 3) are fixed in this version. Its scripts are in review/: check.py (networkx + standard library; run python3 check.py fam|kappa|part2) and extra.py (imports check.py; standard library otherwise; run python3 extra.py famB|g1, and its function insertion_famB() for the insertion tests); both read the certificate file data/part2_certificates.json by a path relative to their own folder. All of these were re-run successfully here.
6. Sources
Marks: † = read only through a summary/snippet (fetch tool or secondary source), not the primary text.
- J. Mazák, F. Zrubák, Circular chromatic index of small graphs, arXiv:2603.08822v1, 9 March 2026, https://arxiv.org/abs/2603.08822 . Quotes above were obtained from the HTML version through a web-fetch tool that returns short verbatim excerpts; they were not compared with the PDF character by character. †(partially)
- A. Hackmann, A. Kemnitz, The circular chromatic index, Discrete Math. 286 (2004) 89–93 — reference [11] of (1), cited there for . † (not read; Lemma 1 is proved here directly)
- X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371–410, doi:10.1016/S0012-365X(00)00217-X. † (bibliographic data only; standard facts , attained by a -colouring; not needed for the proof)
- A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551–559. † (origin of -colourings; not needed)
- M. E. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970) 23–29, doi:10.1016/S0021-9800(70)80005-9. † — its Theorem "in a connected vertex-transitive graph, distinct atoms are vertex-disjoint" is as stated in D. W. Morris et al.'s note https://www.cs.uleth.ca/~morris/Research/SpecialFamily.pdf (Theorem 1.1 there, attributed to Watkins). Lemma 3 above is proved independently.
- W. Mader — the atom lemma is often attributed jointly to Mader (early 1970s, Arch. Math.). † (exact reference not verified)
- Y. O. Hamidoune, Sur les atomes d'un graphe orienté, C. R. Acad. Sci. Paris Sér. A 284 (1977) 1253–1256 (bibliographic data from the reference list of arXiv:math/0603504). † (content not read; Lemma 4 is proved here directly)
- M.-Z. quote Lukoťka–Mazák, Cubic graphs with given circular chromatic index (2010), for the case of Problem 6. †
7. Further searches (Part 2; computer-certified examples, no new general theorem)
All statements here are verified by verify_part2.py (standard library; reads data/part2_certificates.json; prints ALL PART 2 CHECKS PASSED). "Perfect" colouring: a -colouring of a graph of odd order in which every window of consecutive classes is a matching of size ; then exactly by Lemmas 1–2. Search scripts are in search/ (SAT via python-sat/CaDiCaL; work log search/LOG.md).
7.1 A structural lemma (proved, elementary). In a perfect -colouring let be the vertex missed by window . Since window = window minus class plus class , we get . In the cyclic ansatz of search/cyc2.py (class = class, colour ) colour corresponds to , so consecutive base vertex sets differ by at most one exchanged vertex, and after steps (at most exchanges). Since for the number of maximal cyclic runs of equals : each base vertex set is a union of at most cyclic intervals. Adding these implied constraints sped the SAT search up by about two orders of magnitude (e.g. : 8.5 s to 0.1 s).
7.2 New regular examples (cyclic ansatz), all with (atom argument of 2.5, and max-flow): - : 18-regular, . Denominator 5 with a simple regular graph (); Mazák–Zrubák have only for multigraphs with (). Base classes , , , class, colour . ( is prime, so by Lemma 4.) Note: same connection set as Theorem 2 but on 31 vertices. - : 24-regular, (also covered by Theorem 1 as , but with ).
7.3 Non-regular examples, (remark ""). Insertion lemma (proved): if is a perfect -colouring of and are matchings of the complement of with , then inserting before colour gives a perfect -colouring of (every new window is, as a family of vertex sets, a permutation of an old window). Mirror form: the same holds if instead , i.e. the block copies the classes before the insertion point; proof: reversing the colour order maps perfect -colourings to perfect -colourings and exchanges the two forms. Several insertions at once: if insertion points are separated by at least old classes, no window meets two blocks, so the window structure is preserved; for the result to be a simple graph the blocks must in addition be pairwise edge-disjoint (each later block consists of matchings in the complement of plus the earlier blocks). Each insertion raises all degrees but one by 1. Family B: , base -colouring with the cyclic ansatz and , (these satisfy the four window conditions (C1)–(C4) of 2.3, checked by hand as there), and base graph without edges of length 1. Then the windows starting at colours 0 and 6 consist of unions of intervals of even length, perfectly matched by the length-1 edges with , resp. (disjoint sets of , so the two blocks are edge-disjoint, as the several-insertions hypothesis requires; the insertion points are 6 classes apart), giving and with . The only missing ingredient for a theorem for all is the base matching problem: perfect matchings of and with pairwise distinct lengths, none equal to 1 (a Skolem/Langford-type problem; internal lengths must be exactly ). Solved by SAT for (certificates stored); UNSAT for ; not solved within 60 s; no uniform construction found yet (the obvious nested choices fail, checked by hand). Certified values: (all in ). Separately, a generalised insertion search gave a graph with , , ; its block (inserted before colour 0) copies the vertex sets of colours 59, 60, 61 of the base, so it is an instance of the mirror form of the insertion lemma (it is also checked directly as a perfect -colouring by verify_part2.py).
7.4 Exhaustively excluded (UNSAT, cyclic ansatz with , i.e. complete up to translation): = (4,3,1), (4,3,2), (5,3,1), (5,4,1), (5,3,2), (5,4,2), (5,4,3), (6,5,1), (6,5,2), (7,4,1), (7,5,1), (7,6,1), (7,5,2), (8,5,1), (8,7,1), (9,5,1), (9,7,1), (9,8,1); undecided in 300 s: (7,4,2), (7,6,2), (8,5,2). Insertion into cyclic bases (one block, inserted vertex sets free): UNSAT for (so no such graph for of this form); : UNSAT with blocks 3 colours apart; Family B with : UNSAT for (blocks 6 apart); one block on the base (): UNSAT. minus (near-perfect matching + one edge), single-edge classes, value : no perfect colouring for . A fully general SAT search for , value () did not finish in 200 s.
Still open after this work: Problem 7 for ; (no example found); ; Problem 6 (non-trivial reading) for , .