## 5 Can\({}_{k}^{\pi}(T_{2n,n})\)  
For \(n\geq 1\), let \(T_{2n,n}\) be the complete \(n\)-partite graph on \(2n\) vertices in which each independent set is size two. Then \(T_{2,1}\cong\overline{K}_{2}\), \(T_{4,2}\cong K_{2,2}\cong C_{4}\), \(T_{6,3}\cong K_{2,2,2}\), and so on. The purpose of this section is to study the canonical \(k\)-colouring graphs of \(T_{2n,n}\). The results proved in this section are summarized in Theorem 4.2 below. In the cases where the canonical colour graph is connected, we describe it completely. Theorem 4.3: _Let \(n\geq 1\). Then_  
1. \(\mbox{\rm Can}_{n}^{\pi}(T_{2n,n})\cong K_{1}\) _for any vertex ordering_ \(\pi\)_._
2. _If_ \(k\geq 2n\)_, then_ \(\mbox{\rm Can}_{k}^{\pi}(T_{2n,n})\cong\mbox{\rm Can}_{2n}^{\pi}(T_{2n,n})\) _for any vertex ordering_ \(\pi\)_._
3. _If_ \(n<k\) _and the subgraph of_ \(T_{2n,n}\) _induced by the first_ \(n\) _vertices in the vertex ordering_ \(\pi\) _is not complete, then_ \(\mbox{\rm Can}_{k}^{\pi}(T_{2n,n})\) _is disconnected._
4. _If_ \(n<k\) _and the subgraph of_ \(T_{2n,n}\) _induced by the first_ \(n\) _vertices in the vertex ordering_ \(\pi\) _is complete, then_ \(\mbox{\rm Can}_{k}^{\pi}(T_{2n,n})\) _is a tree. Further, if_ \(\mbox{\rm Can}_{k}^{\pi}(T_{2n,n})\) _and_ \(\mbox{\rm Can}_{k}^{\phi}(T_{2n,n})\) _are both trees, then_ \(\mbox{\rm Can}_{k}^{\pi}(T_{2n,n})\cong\mbox{\rm Can}_{k}^{\phi}(T_{2n,n})\)_._
5. \(\mbox{\rm Can}_{2n}^{\pi}(T_{2n,n})\) _never has a Hamilton cycle and has a Hamilton path only when_ \(n=2\)_,_ \(k=2\)_._  
Statements 1 and 2 are clear. Statement 3 is immediate by Proposition 1. The proof of statement 4.2 is partitioned into a sequence of propositions. First, we consider the graphs \(\mbox{\rm Can}_{2n}^{\pi}(T_{2n,n})\), for vertex orderings \(\pi\) that start with a maximal clique. The graphs \(\mbox{\rm Can}_{k}^{\pi}(T_{2n,n})\), with \(n<k<2n\), will be considered later. According to statement 2.2 we need not consider the situations in which \(k>2n\). Proposition 5: _Let \(n\geq 1\). If the subgraph of \(T_{2n,n}\) induced by the first \(n\) vertices in the sequence \(\pi\) is complete, then \(\mbox{\rm Can}_{2n}^{\pi}(T_{2n,n})\) is a tree on \(2^{n}\) vertices. Further, if the subgraph of \(T_{2n,n}\) induced by the first \(n\) vertices in the sequence \(\phi\) is complete, then \(\mbox{\rm Can}_{2n}^{\pi}(T_{2n,n})\cong\mbox{\rm Can}_{2n}^{\phi}(T_{2n,n})\)._  
Proof: In any colouring of \(T_{2n,n}\), a pair of independent vertices either has the same colour, or different colours. In the latter case, each vertex in the pair is the only vertex to be assigned that colour. Suppose that the last \(n\) vertices of \(\pi\) are \(x_{1},x_{2},\ldots,x_{n}\). A canonical \(2n\)-colouring with respect to \(\pi\) can be encoded as a binary sequence \(b_{1}b_{2}\ldots b_{n}\) of length \(n\) in which the \(i\)-th element is \(0\) if vertex \(x_{i}\) is assigned the same colour as its unique non-neighbour (which is one of the first \(n\) vertices of \(\pi\)), and \(1\) if it is assigned the first colour not used on a vertex earlier in the sequence. Thus, \(\mbox{\rm Can}_{2n}^{\pi}(T_{2n,n})\) has precisely \(2^{n}\) vertices. We claim that an element \(b_{i}\) of the binary sequence can change (from \(0\) to \(1\), or \(1\) to \(0\)) if and only if \(b_{j}=0\) for all \(j>i\). Suppose that \(x_{i}\) is the only vertex of its colour, that is, it has a different colour than its unique non-neighbour, \(w\), and \(b_{i}=1\). If there exists \(j>i\) such that \(x_{j}\) also has a different colour than its unique non-neighbour, then the colouring arising from assigning the colour of \(w\) to \(x_{i}\) is not canonical (because the colour of \(x_{i}\), which is smaller than the colour of \(x_{j}\), would not be used on any vertex). Similarly, if \(x_{i}\) has the same colour as its unique non-neighbour, then it can only be assigned a different colour if there is no \(j>i\) such that \(x_{j}\) has a different colour than its unique non-neighbour. This proves the claim.