Circular chromatic index of a complete graph minus an edge (Mazák–Zrubák, Conjecture 2)

What Lean checks

Written proof for every even d >= 6, after one independent model referee pass. The standard-library verifier checks Lemmas 2 to 5(1) on all acyclic colourings for d=4 and excludes the edge orderings of Lemma 3 for d=6; optional SAT checks treat d=6 from the definition. No script completed d=8. No proof-assistant formalization is claimed.

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 rr-edge-colouring of a graph GG is a map c:E(G)→[0,r)c:E(G)\to[0,r) such that 1≤|c(e)−c(f)|≤r−11\le|c(e)-c(f)|\le r-1 whenever ee and ff share a vertex. The circular chromatic index χ′c(G)\chi'_c(G) is the least rr for which one exists; it satisfies χ′(G)−1<χ′c(G)≤χ′(G)\chi'(G)-1\lt\chi'_c(G)\le\chi'(G). [MZ, Section 1; Zhu01]

Theorem. Let d≥6d\ge 6 be even and let GG be the complete graph Kd+1K_{d+1} with one edge removed. Then χ′c(G)=d+1\chi'_c(G)=d+1.

This is Conjecture 2 of Mazák and Zrubák [MZ], who verified it by computer for d∈{6,8,10,12}d\in\{6,8,10,12\}. For d=4d=4 the statement is false: χ′c(K5−e)=9/2\chi'_c(K_5-e)=9/2 [MZ]. The proof below shows where d≥6d\ge6 is used (last step).

Throughout, n=d+1=2h−1n=d+1=2h-1 with h=d/2+1≥4h=d/2+1\ge4, G=Kn−uvG=K_n-uv, and

N=|E(G)|=(n2)−1=h(2h−3)=2h(h−2)+h.N=|E(G)|=\binom n2-1=h(2h-3)=2h(h-2)+h .

The vertices u,vu,v are called special (degree n−2n-2), the others normal (degree n−1n-1). Any two normal vertices are adjacent. Since nn is odd, a matching has at most h−1h-1 edges, so χ′(G)≥N/(h−1)>n−1\chi'(G)\ge N/(h-1)\gt n-1, and χ′(G)≤χ′(Kn)=n\chi'(G)\le\chi'(K_n)=n. Hence χ′(G)=n\chi'(G)=n and χ′c(G)≤n\chi'_c(G)\le n. The task is to exclude χ′c(G)<n\chi'_c(G)\lt n.

Step 1. Acyclic colourings

For a proper colouring f:V(H)→ℤkf:V(H)\to\mathbb Z_k of a graph HH let DfD_f be the digraph on V(H)V(H) with an arc x→yx\to y whenever xy∈E(H)xy\in E(H) and f(y)=f(x)+1f(y)=f(x)+1.

Lemma 1 (Guichard [Gui93]; see [Zhu01, Theorem 3.1]). If χc(H)<k=χ(H)\chi_c(H)\lt k=\chi(H), then HH has a proper colouring f:V(H)→ℤkf:V(H)\to\mathbb Z_k for which DfD_f has no directed cycle.

Proof (included for completeness). Since χc(H)<k\chi_c(H)\lt k, there is a circular rr-colouring ψ:V(H)→[0,r)\psi:V(H)\to[0,r) with r<kr\lt k. Here r>k−1r\gt k-1: otherwise ⌊ψ⌋\lfloor\psi\rfloor would be a proper colouring with the k−1k-1 colours 0,…,k−20,\dots,k-2. Put f(x)=⌊ψ(x)⌋∈{0,…,k−1}f(x)=\lfloor\psi(x)\rfloor\in\{0,\dots,k-1\}. Adjacent vertices have |ψ(x)−ψ(y)|≥1|\psi(x)-\psi(y)|\ge1, so ff is proper. For an arc x→yx\to y with f(x)≤k−2f(x)\le k-2 we get ψ(y)>ψ(x)\psi(y)\gt\psi(x), hence ψ(y)−ψ(x)≥1\psi(y)-\psi(x)\ge1. For an arc with f(x)=k−1f(x)=k-1, f(y)=0f(y)=0 we get ψ(y)−ψ(x)≥−(r−1)\psi(y)-\psi(x)\ge-(r-1). A directed cycle passes through the colours cyclically, so it has mkmk arcs of which mm are of the second kind. Summing along the cycle gives 0≥m(k−1)−m(r−1)=m(k−r)>00\ge m(k-1)-m(r-1)=m(k-r)\gt0, a contradiction. ∎

Apply this to the line graph of GG. From now on assume, for a contradiction, that φ:E(G)→ℤn\varphi:E(G)\to\mathbb Z_n is a proper edge-colouring whose digraph D=DφD=D_\varphi is acyclic. The vertices of DD are the edges of GG, and e→fe\to f means that e,fe,f share a vertex and φ(f)=φ(e)+1\varphi(f)=\varphi(e)+1. Write Mi=φ−1(i)M_i=\varphi^{-1}(i).

Step 2. Colour classes, the source and the sink

Lemma 2. After adding a constant to all colours:

  1. |M0|=h−2|M_0|=h-2 and |Mi|=h−1|M_i|=h-1 for i≠0i\ne0. So M0M_0 misses exactly three vertices, forming a set AA, and each other class misses exactly one vertex.
  2. DD has exactly one source f*f^* and exactly one sink g*g^*. Moreover φ(f*)=1\varphi(f^*)=1, φ(g*)=n−1\varphi(g^*)=n-1, and both edges have both ends in AA.

Proof. (1) Each class is a matching, so has at most h−1h-1 edges, and N=n(h−1)−1N=n(h-1)-1. Adding a constant to all colours does not change DD. (2) An edge xyxy of colour ii is a source exactly when no edge at xx or yy has colour i−1i-1, that is when Mi−1M_{i-1} misses both xx and yy. Then i−1=0i-1=0 and x,y∈Ax,y\in A. Two such edges would be disjoint edges of M1M_1 inside the three-element set AA. So there is at most one source, and in the same way at most one sink, of colour n−1n-1 inside AA. A finite acyclic digraph has a source and a sink. ∎

Step 3. The longest-path levels form a linear order

For an edge ee let L(e)L(e) be the number of arcs of a longest directed path of DD ending at ee.

Lemma 3. LL is a bijection from E(G)E(G) onto {0,1,…,N−1}\{0,1,\dots,N-1\}, and φ(e)≡L(e)+1(modn)\varphi(e)\equiv L(e)+1\pmod n. The edges with L=ℓL=\ell and L=ℓ+1L=\ell+1 share a vertex. Finally:

(P) if e,fe,f share a vertex and L(e)<L(f)L(e)\lt L(f), then L(f)−L(e)≢0,−1(modn)L(f)-L(e)\not\equiv 0,-1\pmod n.

Proof. A longest path ending at ee starts at a source (otherwise it could be extended backwards, and in an acyclic digraph the extended walk is again a path), hence at f*f^*, and colours increase by one along arcs. So φ(e)≡L(e)+1\varphi(e)\equiv L(e)+1. Write L(e)=t(e)+nw(e)L(e)=t(e)+n\,w(e) with 0≤t(e)≤n−10\le t(e)\le n-1; thus t=0,1,…,n−2,n−1t=0,1,\dots,n-2,n-1 for the colours 1,2,…,n−1,01,2,\dots,n-1,0. For an arc e→fe\to f we have L(f)≥L(e)+1L(f)\ge L(e)+1, which gives

w(f)≥w(e)always,w(f)≥w(e)+1if φ(e)=0.w(f)\ge w(e)\quad\text{always},\qquad w(f)\ge w(e)+1\quad\text{if }\varphi(e)=0 .

For S⊆MiS\subseteq M_i let N+(S)⊆Mi+1N^+(S)\subseteq M_{i+1} be the set of edges of colour i+1i+1 sharing a vertex with an edge of SS. We claim:

  • (E1) |N+(S)|≥|S||N^+(S)|\ge|S| for S⊆MiS\subseteq M_i, 1≤i≤n−21\le i\le n-2, and for S⊆M0S\subseteq M_0;
  • (E2) |N+(S)|≥|S||N^+(S)|\ge|S| for S⊆Mn−1\{g*}S\subseteq M_{n-1}\setminus\{g^*\}.

Indeed, the edges of SS cover 2|S|2|S| vertices. In (E1) the class Mi+1M_{i+1} misses only one vertex. In (E2) the class M0M_0 misses the three vertices of AA, but two of them are the ends of g*∈Mn−1g^*\in M_{n-1} and are not covered by SS. So in both cases at least 2|S|−12|S|-1 of the covered vertices lie on an edge of the next class, and these edges number at least ⌈(2|S|−1)/2⌉=|S|\lceil(2|S|-1)/2\rceil=|S|.

Let ai(j)a_i(j) be the number of edges e∈Mie\in M_i with w(e)≥jw(e)\ge j. The sets {e∈Mi:w(e)≥j}\{e\in M_i:w(e)\ge j\} are mapped by N+N^+ into the corresponding set of the next class, and into the set with j+1j+1 when i=0i=0. With (E1), (E2):

a1(j)≤a2(j)≤…≤an−1(j),a0(j)≥an−1(j)−1,a1(j+1)≥a0(j).a_1(j)\le a_2(j)\le\dots\le a_{n-1}(j),\qquad a_0(j)\ge a_{n-1}(j)-1,\qquad a_1(j+1)\ge a_0(j).

Hence a1(j+1)≥a1(j)−1a_1(j+1)\ge a_1(j)-1. On the other hand every level ℓ\ell between 00 and Λ=maxL\Lambda=\max L contains an edge (the predecessor on a longest path has level one less), and level njnj consists of the edges of colour 1 with w=jw=j. So a1(j+1)≤a1(j)−1a_1(j+1)\le a_1(j)-1 whenever nj≤Λnj\le\Lambda. Therefore all the inequalities above are equalities for these jj. Let JJ be the least integer with nJ>ΛnJ\gt\Lambda, so that no edge has w≥Jw\ge J. Starting from a1(0)=h−1a_1(0)=h-1 and going down by one at each step we reach a1(J)=0a_1(J)=0, so J=h−1J=h-1. For 0≤j≤h−20\le j\le h-2 we get ai(j)=h−1−ja_i(j)=h-1-j for 1≤i≤n−11\le i\le n-1 and a0(j)=h−2−ja_0(j)=h-2-j, and ai(h−1)=0a_i(h-1)=0 for all ii. So for each colour i≠0i\ne0 and each 0≤j≤h−20\le j\le h-2 there is exactly one edge of colour ii with w=jw=j, and for colour 0 exactly one for each 0≤j≤h−30\le j\le h-3 and none with w=h−2w=h-2. These are (n−1)(h−1)+(h−2)=N(n-1)(h-1)+(h-2)=N edges on the levels 0,…,N−10,\dots,N-1, one on each.

The edge of level ℓ+1\ell+1 has an in-neighbour of level ℓ\ell, so the two share a vertex. For (P): L(f)−L(e)≡0L(f)-L(e)\equiv0 would give two edges of the same colour at a vertex. If L(f)−L(e)≡−1L(f)-L(e)\equiv-1 then φ(e)=φ(f)+1\varphi(e)=\varphi(f)+1, so f→ef\to e is an arc and L(e)>L(f)L(e)\gt L(f). ∎

Let sℓs_\ell be the edge with L=ℓL=\ell. We say that a vertex xx is at position ℓ\ell if x∈sℓx\in s_\ell. Every position holds exactly two vertices. Since each edge of GG has exactly one position:

(M) two normal vertices have exactly one common position; uu and vv have none; a normal and a special vertex have exactly one.

Step 4. Runs

Let p1<…<pdegxp_1\lt\dots\lt p_{\deg x} be the positions of a vertex xx. A run of xx is a maximal set of consecutive integers among them, and kxk_x is the number of runs.

Lemma 4.

  1. For a normal vertex, pj+1−pj≡1(modn)p_{j+1}-p_j\equiv1\pmod n for all jj.
  2. For 0≤ℓ≤N−20\le\ell\le N-2 exactly one vertex is at both positions ℓ\ell and ℓ+1\ell+1. Hence ∑xkx=N+1\sum_x k_x=N+1.
  3. There is exactly one vertex bb in s0∩sN−1s_0\cap s_{N-1}. It is normal and kb=h−1k_b=h-1. Every other normal vertex xx has kx=h−2k_x=h-2, and its first position αx\alpha_x and last position ωx\omega_x satisfy ωx=αx+N−2h\omega_x=\alpha_x+N-2h, so 0≤αx≤2h−10\le\alpha_x\le 2h-1. For every normal vertex, a run ending at ee that is not its last run is followed by a run starting at e+2he+2h; equivalently, a run starting at ss that is not its first run is preceded by a run ending at s−2hs-2h. All runs of uu and of vv have length one.

Proof. (1) Let μ\mu be the colour missing at xx and let eje_j be the edge at xx of colour μ+j\mu+j, 1≤j≤n−11\le j\le n-1. Then ej→ej+1e_j\to e_{j+1} is an arc, so L(ej)<L(ej+1)L(e_j)\lt L(e_{j+1}) and the difference is ≡1\equiv1.

  1. By Lemma 3, sℓs_\ell and sℓ+1s_{\ell+1} are distinct edges sharing a vertex. Counting pairs (vertex, position) gives ∑x(sum of run lengths)=2N\sum_x(\text{sum of run lengths})=2N and ∑x∑runs(length−1)=N−1\sum_x\sum_{\text{runs}}(\text{length}-1)=N-1.

  2. Let xx be normal and write βx=N−1−ωx\beta_x=N-1-\omega_x. By (1), ωx−αx=(n−2)+nTx\omega_x-\alpha_x=(n-2)+nT_x, where TxT_x is the sum of (pj+1−pj−1)/n(p_{j+1}-p_j-1)/n. Steps inside a run contribute 0 and steps between runs at least 1, so Tx≥kx−1T_x\ge k_x-1, with equality exactly when all steps between runs equal n+1=2hn+1=2h. Since N−1−(n−2)=n(h−2)N-1-(n-2)=n(h-2), we get αx+βx=nqx\alpha_x+\beta_x=n\,q_x for an integer qxq_x, and qx≥0q_x\ge0 because αx,βx≥0\alpha_x,\beta_x\ge0. Moreover

kx≤Tx+1=h−1−qx.k_x\le T_x+1=h-1-q_x .

Here qx=0q_x=0 only if x∈s0∩sN−1x\in s_0\cap s_{N-1}, which holds for at most one vertex. Let ε∈{0,1}\varepsilon\in\{0,1\} be the number of normal vertices with qx=0q_x=0. Special vertices have k≤n−2k\le n-2. With (2):

n(h−1)=N+1=∑xkx≤(n−2)(h−1)−(n−2−ε)+2(n−2)=(n−2)h+ε=n(h−1)−1+ε.n(h-1)=N+1=\sum_xk_x\le(n-2)(h-1)-(n-2-\varepsilon)+2(n-2)=(n-2)h+\varepsilon=n(h-1)-1+\varepsilon .

So ε=1\varepsilon=1 and equality holds everywhere: one normal vertex bb has qb=0q_b=0 and kb=h−1k_b=h-1; every other normal xx has qx=1q_x=1, that is αx+βx=n\alpha_x+\beta_x=n, and kx=h−2k_x=h-2; all steps between runs of normal vertices equal 2h2h; and ku=kv=n−2k_u=k_v=n-2, which is the number of edges at uu and at vv. ∎

For 1≤ℓ≤N−11\le\ell\le N-1 let start(ℓ)\mathrm{start}(\ell) be the vertex of sℓs_\ell not in sℓ−1s_{\ell-1}, and for 0≤ℓ≤N−20\le\ell\le N-2 let end(ℓ)\mathrm{end}(\ell) be the vertex of sℓs_\ell not in sℓ+1s_{\ell+1}. By Lemma 4(3), a special vertex at position ℓ\ell equals start(ℓ)\mathrm{start}(\ell) and end(ℓ)\mathrm{end}(\ell) whenever these are defined. In particular:

(C) the vertex common to sℓs_\ell and sℓ+1s_{\ell+1} is always normal; and if ℓ\ell is a position of a special vertex and yy is the normal vertex of sℓs_\ell, then y∈sℓ−1y\in s_{\ell-1} (if ℓ≥1\ell\ge1) and y∈sℓ+1y\in s_{\ell+1} (if ℓ≤N−2\ell\le N-2).

Step 5. The table with 2h2h columns

Write every position as ℓ=2hρ+c\ell=2h\rho+c with row ρ≥0\rho\ge0 and column c∈{0,…,2h−1}c\in\{0,\dots,2h-1\}. Since N=2h(h−2)+hN=2h(h-2)+h, the columns c≤h−1c\le h-1 (the left half) have the rows 0,…,h−20,\dots,h-2 and the columns c≥hc\ge h (the right half) have the rows 0,…,h−30,\dots,h-3. A position is special if it holds uu or vv.

Lemma 5.

  1. The special positions are exactly the positions in four columns r1,r2,r1+h,r2+hr_1,r_2,r_1+h,r_2+h with r1≠r2r_1\ne r_2 in {0,…,h−1}\{0,\dots,h-1\}.
  2. Let P={0,…,h−1}\{r1,r2}P=\{0,\dots,h-1\}\setminus\{r_1,r_2\}, so |P|=h−2|P|=h-2. Every column α∈P∪(P+h)\alpha\in P\cup(P+h) is the first position of exactly one normal vertex xα≠bx_\alpha\ne b, and these are all the normal vertices other than bb.
  3. Let xx be normal with first position α\alpha, and put gmax=hg_{\max}=h if x≠bx\ne b and gmax=h−1g_{\max}=h-1 if x=bx=b. There are integers 0=i−(0)≤i+(0)=i−(1)≤i+(1)=…≤i+(gmax)=kx−10=i^-(0)\le i^+(0)=i^-(1)\le i^+(1)=\dots\le i^+(g_{\max})=k_x-1 such that the positions of xx are exactly

α+g+2hi,0≤g≤gmax,i−(g)≤i≤i+(g),\alpha+g+2h\,i,\qquad 0\le g\le g_{\max},\quad i^-(g)\le i\le i^+(g),

and xx is at both ℓ\ell and ℓ+1\ell+1 exactly for ℓ=α+g+2hi+(g)\ell=\alpha+g+2h\,i^+(g), 0≤g<gmax0\le g\lt g_{\max}. If the column of α+g\alpha+g is special, then i−(g)=i+(g)i^-(g)=i^+(g).

Proof. We first prove the description of the positions in (3), then (1) except for the form r1+h,r2+hr_1+h,r_2+h 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 pj+1−pjp_{j+1}-p_j of xx are 1 or 2h2h, and there are kx−1k_x-1 steps of the second kind. Let gg count the steps of the first kind and ii those of the second kind made so far. This gives the description; the final value of gg is (n−2)−(kx−1)(n-2)-(k_x-1), which is hh for x≠bx\ne b and h−1h-1 for bb.

(1), closure and count. Let ℓ\ell be special, holding the special vertex σ\sigma, and let ℓ+2h≤N−1\ell+2h\le N-1. Put z=start(ℓ+2h)z=\mathrm{start}(\ell+2h). If zz were normal, its run starting at ℓ+2h\ell+2h would not be its first, since first positions are at most 2h−12h-1. So its previous run ends at ℓ\ell (Lemma 4(3)), hence z=end(ℓ)=σz=\mathrm{end}(\ell)=\sigma, a contradiction. So ℓ+2h\ell+2h is special. Symmetrically, if ℓ−2h≥0\ell-2h\ge0 then z=end(ℓ−2h)z=\mathrm{end}(\ell-2h) is special: a normal zz would not be in its last run, since last positions are at least N−2hN-2h, and its next run would start at ℓ\ell, giving z=start(ℓ)=σz=\mathrm{start}(\ell)=\sigma. Hence the set of special positions is a union of whole columns. There are 2(n−2)=4h−62(n-2)=4h-6 special positions, a left column has h−1h-1 positions and a right column h−2h-2. If there are σ1\sigma_1 left and σ2\sigma_2 right special columns, then σ1(h−1)+σ2(h−2)=4h−6\sigma_1(h-1)+\sigma_2(h-2)=4h-6, that is (h−2)(σ1+σ2−4)=2−σ1(h-2)(\sigma_1+\sigma_2-4)=2-\sigma_1. With 0≤σ1,σ2≤h0\le\sigma_1,\sigma_2\le h and h≥4h\ge4 the only solution is σ1=σ2=2\sigma_1=\sigma_2=2: the right side lies between 2−h2-h and 22 and is divisible by h−2≥2h-2\ge2, so it is 00 (giving σ1=2\sigma_1=2, σ2=2\sigma_2=2) or −(h−2)-(h-2) (giving σ1=h\sigma_1=h, σ2=3−h<0\sigma_2=3-h\lt0), or, for h=4h=4 only, 22 (giving σ1=0\sigma_1=0, σ2=5>h\sigma_2=5\gt h).

(2), and the form of the special columns. The first positions of the n−3=2h−4n-3=2h-4 normal vertices other than bb lie in {0,…,2h−1}\{0,\dots,2h-1\} (Lemma 4). They are distinct, because for ℓ≥1\ell\ge1 only start(ℓ)\mathrm{start}(\ell) can have first position ℓ\ell, and position 0 holds bb and one other vertex. None of them is special: at a special position ℓ≥1\ell\ge1 the starting vertex is special, and a special position 0 holds bb and a special vertex. As exactly 2h−42h-4 columns are not special, each of them is the first position of exactly one such vertex. The last position of xαx_\alpha is α+N−2h≡α+h(mod2h)\alpha+N-2h\equiv\alpha+h\pmod{2h}. It is not special: otherwise it is not N−1N-1 (because sN−1s_{N-1} would then consist of bb and the normal vertex xαx_\alpha), and then (C) puts xαx_\alpha at the next position as well. So the set of non-special columns is closed under adding hh modulo 2h2h, which gives the form of the special columns in (1) and of PP.

Last sentence of (3). Let the column of α+g\alpha+g (that is, (α+g)mod2h(\alpha+g)\bmod 2h) be special. By (1) the position α+g+2hi−(g)\alpha+g+2h\,i^-(g) is then special. If i+(g)>i−(g)i^+(g)\gt i^-(g), then xx is not at the next position, against (C). ∎

For p∈Pp\in P we call xpx_p unwrapped and xp+hx_{p+h} wrapped. By Lemma 5(3):

  • bb has its positions in the columns 0,…,h−10,\dots,h-1;
  • xpx_p in the columns p,…,p+hp,\dots,p+h, and its position p+g+2hip+g+2hi is in row ii;
  • xp+hx_{p+h} in the columns p+h,…,2h−1p+h,\dots,2h-1 (row ii) and 0,…,p0,\dots,p (row i+1i+1).

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 2h−12h-1 (position 2hρ+2h−12h\rho+2h-1 is followed by position 2h(ρ+1)2h(\rho+1)). We call jx(g)=i+(g)−i−(g)j_x(g)=i^+(g)-i^-(g) the number of junctions of xx at gg. Thus ∑gjx(g)=h−3\sum_gj_x(g)=h-3 for x≠bx\ne b, and junctions occur only in non-special columns.

Rows at a boundary. For a column c∈{0,…,h−2}c\in\{0,\dots,h-2\} and a normal vertex zz that is at positions 2hρ+c2h\rho+c and 2hρ+c+12h\rho+c+1 for some ρ\rho, this ρ\rho is unique by Lemma 5(3); call it ρc(z)\rho_c(z). By Lemma 5(3) the vertices for which it exists are bb, the xpx_p with p≤cp\le c and the xp+hx_{p+h} with p>cp\gt c (p∈Pp\in P). These are h−1h-1 vertices. For each of them the value lies in {0,…,h−2}\{0,\dots,h-2\}, because the left column cc has exactly these rows. Conversely, each of the h−1h-1 positions 2hρ+c2h\rho+c, 0≤ρ≤h−20\le\rho\le h-2, is at most 2h(h−2)+h−2=N−22h(h-2)+h-2=N-2, 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 ρc\rho_c equal to ρ\rho. So:

(B) for 0≤c≤h−20\le c\le h-2, ρc\rho_c is a bijection from {b}∪{xp:p≤c}∪{xp+h:p>c}\{b\}\cup\{x_p:p\le c\}\cup\{x_{p+h}:p\gt c\} onto {0,…,h−2}\{0,\dots,h-2\}.

In the same way the rows in which the xpx_p (p∈Pp\in P) pass from column h−1h-1 to column hh are distinct and at most h−3h-3; call them ρh−1(xp)\rho_{h-1}(x_p). And the rows in which the xp+hx_{p+h} arrive in column 0 are distinct and at least 1; call them ρ−1(xp+h)\rho_{-1}(x_{p+h}). Put also ρ−1(b)=0\rho_{-1}(b)=0, ρh−1(b)=h−2\rho_{h-1}(b)=h-2, ρp−1(xp)=0\rho_{p-1}(x_p)=0 and ρp(xp+h)=h−2\rho_p(x_{p+h})=h-2. These conventions do not clash with the values defined before: the list in (B) for the column p−1p-1 does not contain xpx_p, the list for the column pp does not contain xp+hx_{p+h}, and bb occurs neither among the vertices passing from column h−1h-1 to column hh nor among those arriving in column 0 from column 2h−12h-1. With these conventions, for every normal vertex zz and every left column cc that it visits:

(R) the set Rc(z)R_c(z) of rows of zz in column cc is the interval [ρc−1(z),ρc(z)][\rho_{c-1}(z),\rho_c(z)].

(For xpx_p in its first column this says that it starts in row 0; for xp+hx_{p+h} in its last column pp, that it ends in row h−2h-2, the row of its last position; for bb, that it starts at position 0 and ends at N−1N-1.) A consequence:

(O) if y,zy,z both visit the left column cc and ρc−1(y)<ρc−1(z)\rho_{c-1}(y)\lt\rho_{c-1}(z) while ρc(y)>ρc(z)\rho_c(y)\gt\rho_c(z), then Rc(z)⊆Rc(y)R_c(z)\subseteq R_c(y), so yy and zz have a common position in column cc.

Step 6. The vertex bb separates unwrapped from wrapped vertices

Let π(c)=|P∩{0,…,c}|\pi(c)=|P\cap\{0,\dots,c\}|, with π(−1)=0\pi(-1)=0.

Lemma 6. Let 0≤c≤h−20\le c\le h-2 and p∈Pp\in P. If p≤cp\le c then ρc(xp)<ρc(b)\rho_c(x_p)\lt\rho_c(b). If p>cp\gt c then ρc(xp+h)>ρc(b)\rho_c(x_{p+h})\gt\rho_c(b). Consequently ρc(b)=π(c)\rho_c(b)=\pi(c), the xpx_p with p≤cp\le c occupy the rows 0,…,π(c)−10,\dots,\pi(c)-1 at this boundary, and the xp+hx_{p+h} with p>cp\gt c occupy the rows π(c)+1,…,h−2\pi(c)+1,\dots,h-2.

Proof. By (B), distinct vertices have distinct values of ρc\rho_c, so in the comparisons below "not greater" means "smaller" and conversely. Suppose ρc0(xp)>ρc0(b)\rho_{c_0}(x_p)\gt\rho_{c_0}(b) for some c0∈[p,h−2]c_0\in[p,h-2] and take c0c_0 minimal. Then bb and xpx_p have a common position in column c0c_0: for c0=pc_0=p because Rp(xp)=[0,ρp(xp)]⊇[ρp−1(b),ρp(b)]R_p(x_p)=[0,\rho_p(x_p)]\supseteq[\rho_{p-1}(b),\rho_p(b)], and for c0>pc_0\gt p by (O). If ρc(xp)<ρc(b)\rho_c(x_p)\lt\rho_c(b) for some c∈(c0,h−2]c\in(c_0,h-2], the least such cc gives, by (O), a common position in column c≠c0c\ne c_0. Otherwise ρh−2(xp)>ρh−2(b)\rho_{h-2}(x_p)\gt\rho_{h-2}(b), and then Rh−1(xp)=[ρh−2(xp),ρh−1(xp)]⊆[ρh−2(b),h−2]=Rh−1(b)R_{h-1}(x_p)=[\rho_{h-2}(x_p),\rho_{h-1}(x_p)]\subseteq[\rho_{h-2}(b),h-2]=R_{h-1}(b) because ρh−1(xp)≤h−3\rho_{h-1}(x_p)\le h-3; this is a common position in column h−1≠c0h-1\ne c_0. Both cases contradict (M).

Suppose ρc0(xp+h)<ρc0(b)\rho_{c_0}(x_{p+h})\lt\rho_{c_0}(b) for some c0∈[0,p−1]c_0\in[0,p-1] and take c0c_0 maximal. Then there is a common position in column c0+1c_0+1: for c0+1=pc_0+1=p because Rp(xp+h)=[ρp−1(xp+h),h−2]⊇Rp(b)R_p(x_{p+h})=[\rho_{p-1}(x_{p+h}),h-2]\supseteq R_p(b), and otherwise by (O). If ρc(xp+h)>ρc(b)\rho_c(x_{p+h})\gt\rho_c(b) for some c∈[0,c0)c\in[0,c_0), the largest such cc gives a common position in column c+1≤c0c+1\le c_0. Otherwise ρ0(xp+h)<ρ0(b)\rho_0(x_{p+h})\lt\rho_0(b) and R0(xp+h)=[ρ−1(xp+h),ρ0(xp+h)]⊆[0,ρ0(b)]=R0(b)R_0(x_{p+h})=[\rho_{-1}(x_{p+h}),\rho_0(x_{p+h})]\subseteq[0,\rho_0(b)]=R_0(b), a common position in column 0≠c0+10\ne c_0+1. Again (M) is contradicted.

The last sentence follows from (B). ∎

So Rc(b)=[π(c−1),π(c)]R_c(b)=[\pi(c-1),\pi(c)] for every left column cc: one row if c∉Pc\notin P, and the two rows k−1,kk-1,k if cc is the kk-th element of PP.

Step 7. Where the other vertices have their junctions

Write P={p1<p2<…<ph−2}P=\{p_1\lt p_2\lt\dots\lt p_{h-2}\}.

Lemma 7. For 1≤m≤h−21\le m\le h-2:

  1. Rpm(xpm)=[0,m−1]R_{p_m}(x_{p_m})=[0,m-1] and Rpm(xpm+h)=[m,h−2]R_{p_m}(x_{p_m+h})=[m,h-2];
  2. xpmx_{p_m} has m−1m-1 junctions at g=0g=0, h−2−mh-2-m junctions at g=hg=h, and no others. So it occupies the rows 0,…,m−10,\dots,m-1 of column pmp_m, row m−1m-1 of the columns pm+1,…,pm+h−1p_m+1,\dots,p_m+h-1, and the rows m−1,…,h−3m-1,\dots,h-3 of column pm+hp_m+h.

Proof. (1) By (M), bb and xpmx_{p_m} have exactly one common position, in a left column c≥pmc\ge p_m. By Lemma 6 and the bound ρh−1(xpm)≤h−3=π(h−1)−1\rho_{h-1}(x_{p_m})\le h-3=\pi(h-1)-1, the rows of xpmx_{p_m} in column cc are at most π(c)−1\pi(c)-1. So a common row exists only if c=pkc=p_k for some k≥mk\ge m and ρpk(xpm)=k−1\rho_{p_k}(x_{p_m})=k-1. For a given kk at most one mm has this property, by (B) (and by the distinctness of the ρh−1(xp)\rho_{h-1}(x_p) when pk=h−1p_k=h-1). So m↦km\mapsto k is an injective map of {1,…,h−2}\{1,\dots,h-2\} into itself with k≥mk\ge m, hence the identity. Thus ρpm(xpm)=m−1\rho_{p_m}(x_{p_m})=m-1.

Likewise bb and xpm+hx_{p_m+h} have exactly one common position, in a left column c≤pmc\le p_m, and the rows of xpm+hx_{p_m+h} in column cc are at least π(c−1)+1\pi(c-1)+1. (For c≥1c\ge1 this is Lemma 6 at the column c−1c-1; for c=0c=0 it is the bound ρ−1(xpm+h)≥1\rho_{-1}(x_{p_m+h})\ge1 of Step 5.) A common row exists only if c=pkc=p_k with k≤mk\le m and ρpk−1(xpm+h)=k\rho_{p_k-1}(x_{p_m+h})=k. For a given kk at most one mm qualifies, by (B) at the column pk−1p_k-1 (and by the distinctness of the arrival rows ρ−1(xp+h)\rho_{-1}(x_{p+h}) when pk=0p_k=0). So m↦km\mapsto k is injective with k≤mk\le m, hence the identity, and ρpm−1(xpm+h)=m\rho_{p_m-1}(x_{p_m+h})=m.

  1. The vertices x=xpmx=x_{p_m} and y=xpm+hy=x_{p_m+h} visit the columns pm,…,pm+hp_m,\dots,p_m+h and pm+h,…,2h−1,0,…,pmp_m+h,\dots,2h-1,0,\dots,p_m respectively, so their common columns are pmp_m and pm+hp_m+h. By (1) they have no common row in column pmp_m, so by (M) they have one in column pm+hp_m+h. There xx has the rows [h−3−jx(h),h−3][h-3-j_x(h),\,h-3] and yy the rows [0,jy(0)][0,j_y(0)]. By (1), jx(0)=m−1j_x(0)=m-1 and jy(h)=h−2−mj_y(h)=h-2-m, so jx(h)≤h−2−mj_x(h)\le h-2-m and jy(0)≤m−1j_y(0)\le m-1, that is

h−3−jx(h)≥m−1≥jy(0).h-3-j_x(h)\ \ge\ m-1\ \ge\ j_y(0).

A common row forces equality in both places. Then all h−3h-3 junctions of xx are at g=0g=0 and g=hg=h. ∎

Step 8. The contradiction

Since h≥4h\ge4, the set PP has at least two elements p1<p2p_1\lt p_2. By Lemma 7(2):

  • xp1x_{p_1} is in row 0 of every column p1,…,p1+h−1p_1,\dots,p_1+h-1 and in the rows 0,…,h−30,\dots,h-3 of column p1+hp_1+h;
  • xp2x_{p_2} is in the rows 0,10,1 of column p2p_2, in row 1 of the columns p2+1,…,p2+h−1p_2+1,\dots,p_2+h-1, and in the rows 1,…,h−31,\dots,h-3 of column p2+hp_2+h.

Now p1<p2≤h−1<p1+h<p2+hp_1\lt p_2\le h-1\lt p_1+h\lt p_2+h. So both vertices are at the position in row 0 and column p2p_2, and both are at the position in row 1 and column p1+hp_1+h (note 1≤h−31\le h-3). These are two different positions, which contradicts (M). Hence no proper nn-edge-colouring of GG has an acyclic digraph, and by Lemma 1, χ′c(G)=n=d+1\chi'_c(G)=n=d+1. ∎

Remark (d=4d=4). For h=3h=3 the set PP has one element and Step 8 has nothing to compare. Steps 2 to 4 remain valid for h=3h=3, and acyclic colourings exist (for h=3h=3 the counting argument in Lemma 5(1) is not conclusive, but verify.py confirms its statement on all acyclic colourings). With vertices u,v,b,x,yu,v,b,x,y, the order

ub,xb,vx,ux,xy,vy,uy,yb,vbub,\ xb,\ vx,\ ux,\ xy,\ vy,\ uy,\ yb,\ vb

with colours 1,2,3,4,0,1,2,3,41,2,3,4,0,1,2,3,4 is one. By the converse direction of Guichard's theorem [Zhu01, Theorem 3.1], which we do not prove here, an acyclic colouring gives χ′c(K5−uv)<5\chi'_c(K_5-uv)\lt5, in accordance with the value 9/29/2 of [MZ].

What is new

The Theorem, for all even d≥6d\ge6. Mazák and Zrubák state it as a conjecture and report a computer verification for d≤12d\le12 [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.py takes about 10 seconds). Part A enumerates all 2160 proper 5-edge-colourings of K5−eK_5-e, 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 d=4d=4 (and 5⋅12⋅3=1805\cdot12\cdot3=180, with 5 rotations of the colours and 12 automorphisms), and none for d=6d=6.
  • verify_sat.py (needs python-sat) checks directly from the definition, without using any lemma, that K7−eK_7-e has no proper 7-edge-colouring with acyclic digraph (38 s), and that K5−eK_5-e 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 K5−eK_5-e, 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; d=6d=6 is unsatisfiable (224 s).
    • relaxed.py 3 4 5: enumerates, for h=3,4,5h=3,4,5, 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 h=4,5h=4,5 none has every pair of normal vertices meeting exactly once.
    • arith.py: the identities for NN and the counting in Lemma 5(1) for 3≤h≤203\le h\le20.

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 pk=0p_k=0), and for the correction of one sentence in Step 5 that was not used.

The computer check of [MZ] covers d≤12d\le12; our scripts cover only d=6d=6 directly (we did not complete a run for d=8d=8).

Sources

  • [MZ] J. Mazák and F. Zrubák, Circular chromatic index of small graphs, arXiv:2603.08822 (March 2026). Conjecture 2; the value 9/29/2 for K5−eK_5-e; 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 χc\chi_c and the statement of Guichard's theorem.

† marks a source we did not read directly.