## 4 Bipartite Graphs
Hence assume the first \(r\) vertices of \(\pi\) induce a maximum clique. The argument above shows that the cut vertex \(c\) actually partitions the colourings into \(r\) cells, corresponding to using the \(r+1\) colour in each of the \(r\) independent sets. Thus there can be no Hamilton path if there are at least three independent sets with at least two vertices each. By Proposition 4, for \(m,n\geq 2\) and \(k\geq 3\), the graph \(\mathrm{Can}_{k}^{\pi}(K_{m,n})\) has a cut vertex, and hence no Hamilton cycle. On the other hand, for \(n\geq 2\), the graph \(\mathrm{Can}_{k}^{\pi}(K_{1,n})\) has a Hamilton cycle for all \(k\geq 3\)[1]. The possibility remains that the canonical \(k\)-colouring graphs of complete bipartite graphs which are not stars have a Hamilton path. We show next that \(\mathrm{Can}_{k}^{\pi}(K_{n,m})\) in fact has a Hamilton path for all admissible values of \(m,n,k\). To do so, we first give a Gray code (not cyclic) for \(\mathrm{Can}_{k}^{\pi}(\overline{K}_{n})\) which has certain properties. The proof is recursive and similar to, but more elaborate than, that of Theorem 1. Theorem 4: _For all \(n\geq 2\) and \(k\geq 2\), and any vertex ordering \(\pi\), the graph \(\mathrm{Can}_{k}^{\pi}(\overline{K}_{n})\) has a Hamilton path \(x_{1},x_{2},\ldots,x_{t}\) such that:_  
1. _the colouring_ \(x_{1}=11\ldots 1\)_, and the colouring_ \(x_{t}\) _uses all_ \(k\) _colours._
2. _For each_ \(1<i<t\)_, the set of colours used by_ \(x_{i}\) _is identical to the set used by either_ \(x_{i-1}\)_,_ \(x_{i+1}\)_._  
Proof: The sequences 11 and 11, 12 clearly work for \(\mathrm{Can}_{1}^{\pi}(\overline{K}_{2})\) and \(\mathrm{Can}_{2}^{\pi}(\overline{K}_{2})\) respectively. We induct first on \(n\) and then on \(k\). Note that because colourings are canonical we only consider \(n\geq k\). Let \(c_{1},c_{2},\ldots,c_{t}\) be a Hamilton path in \(\mathrm{Can}_{k}^{\pi}(\overline{K}_{n})\) with properties (i) and (ii). For \(i=1,2,\ldots,t\), let \(c_{i}\cdot\ell\) denote the extension of \(c_{i}\) to a canonical \(k\)-colouring of \(\overline{K}_{n+1}\) in which the last vertex is assigned colour \(\ell\). Observe that \(c_{i}\cdot\ell\) is adjacent to \(c_{i+1}\cdot\ell\) whenever both of these are canonical colourings. First the special case \(k=2\). For \(n\geq k=2\) a Hamilton path in \(\mathrm{Can}_{k}^{\pi}(\overline{K}_{n+1})\) is constructed from the one for \(\mathrm{Can}_{k}^{\pi}(\overline{K}_{n})\) as follows: \(c_{1}\cdot 1,c_{1}\cdot 2,c_{2}\cdot 2,c_{2}\cdot 1,c_{3}\cdot 1,c_{3} \cdot 2,\ldots c_{2i}\cdot 2,c_{2i}\cdot 1,c_{2i+1}\cdot 1,c_{2i+1}\cdot 2\cdots\). For \(n\geq k\geq 3\), a Hamilton path in \(\mathrm{Can}_{k}^{\pi}(\overline{K}_{n+1})\) can be constructed from the one for \(\mathrm{Can}_{k}^{\pi}(\overline{K}_{n})\) as follows. The first vertices are \(c_{1}\cdot 1,c_{1}\cdot 2,c_{2}\cdot 2,c_{2}\cdot 1,c_{2}\cdot 3,c_{3}\cdot 3,c_{3} \cdot 2,c_{3}\cdot 1\). Starting with \(i=4\), and then repeating for the next unused prefix \(c_{i}\), suppose \(c_{i},c_{i+1},\ldots,c_{i+j}\) is a maximal sequence such that each \(c_{i+m}\) uses exactly the same set of colours, and suppose the maximum allowable colour that can be added to each of them is \(\ell_{i}\). We construct a Hamilton path on the subgraph induced by \(\{c_{i+m}\cdot\ell|m=0,1,\ldots,j;1\leq\ell\leq\ell_{i}\}\). These will be pieced together to get the Hamilton path for \(\mathrm{Can}_{k}^{\pi}(\overline{K}_{n+1})\). This path must start with \(c_{i}\cdot 1\) and end with \(c_{i+j}\cdot 1\). Suppose \(j\) is odd. Take everything from each prefix \(c_{i+m}\) before proceeding to the next prefix. In particular take the Hamilton path starting at \(c_{i+2p}\cdot 1\) and ending with \(c_{i+2p}\cdot\ell_{i}\) for \(p=0,1,\ldots,j/2\) and in the reverse order \(c_{i+2p+1}\cdot\ell_{i}\) and ending with \(c_{i+2p+1}\cdot 1\) for \(p=0,1,\ldots,j/2\). Suppose \(j\) is even. Recall that for \(1\leq m\leq j\), the subgraph induced by \(\{c_{i+m}\cdot\ell:1\leq\ell\leq\ell_{i}\}\) is complete, and by assumption \(\ell_{i}\geq 3\).