## 3 Unions and Joins
A Hamilton cycle in \(\operatorname{Can}_{k}^{\pi^{\prime}}(G\cup K_{1})\) can be constructed as follows. The first vertex is \(c_{1}\cdot 1\). Then, for \(i=2,3,\dots,t-1\), list all extensions of \(c_{i}\) such that \(c_{i}\cdot 1\) is first and \(c_{i}\cdot 2\) is last if \(i\) is even, and \(c_{i}\cdot 2\) is first and \(c_{i}\cdot 1\) is last if \(i\) is odd. Observe that any pair of consecutive vertices in the list are adjacent. Let \(c_{t-1}\cdot 2\) be the last vertex listed according to this procedure. The Hamilton cycle is completed by listing \(c_{t}\cdot z\), then all other extensions of \(c_{t}\) in such a way that \(c_{t}\cdot 3\) is listed last and, finally, \(c_{1}\cdot 3\) and all extensions of \(c_{1}\) in such a way that \(c_{1}\cdot 1\) is listed last (recall that \(c_{1}\cdot 1\) was the first vertex listed). This completes the proof. Corollary 1: _Let \(\pi\) be a vertex ordering such that \(\operatorname{Can}_{k}^{\pi}(G)\) is Hamiltonian. Then, for the vertex ordering \(\pi^{\prime}\) of \(G\cup\overline{K}_{n}\) obtained by placing the vertices of \(\overline{K}_{n}\) at the end of \(\pi\), the graph \(\operatorname{Can}_{k}^{\pi^{\prime}}(G\cup\overline{K}_{n})\) is Hamiltonian._  
The Gray code for set partitions implied by the following is similar to the one found by [PERSON] [2]. Corollary 2: _For all \(n\geq 3\) and \(k\geq 2\), and any vertex ordering \(\pi\), the graph \(\operatorname{Can}_{k}^{\pi}(\overline{K}_{n})\) is Hamiltonian._  
We now turn our attention to connectivity of the canonical \(k\)-colouring graph of the disjoint union of graphs \(G_{1}\) and \(G_{2}\). Since it is an open problem to determine general conditions under which the canonical \(k\)-colouring graph of a (connected) graph \(G\) is connected, in the results that follow we assume the canonical \(k\)-colouring graph of \(G_{1}\) is connected and give conditions under which a canonical colouring graph of \(G_{1}\cup G_{2}\) is connected, no matter how the vertices of \(G_{2}\) are ordered following the vertex ordering of \(G_{1}\). Theorem 4.1: _Let \(G_{1}\) and \(G_{2}\) be disjoint graphs such that \(\chi(G_{1})\geq 1+col(G_{2})\). Suppose there exists an integer \(k\), and an ordering \(\phi\) of the vertices of \(G_{1}\), such that \(\operatorname{Can}_{k}^{\pi}(G_{1})\) is connected. Then, for any ordering \(\pi\) of the vertices of \(G_{1}\cup G_{2}\) obtained by putting an ordering of the vertices of \(G_{2}\) after \(\phi\), the graph \(\operatorname{Can}_{k}^{\pi}(G_{1}\cup G_{2})\) is connected._  
Proof: Let \(c\) be some particular canonical colouring of \(G_{1}\cup G_{2}\) with \(\chi(G_{1})=\chi(G_{1}\cup G_{2})\) colours such that colours \(1,2,\ldots,\chi(G_{1})\) appear on the vertices of \(G_{1}\) (as they must), and colours \(1,2,\ldots,\chi(G_{2})\) appear on the vertices of \(G_{2}\). Let \(c_{2}\) be the restriction of \(c\) to \(V(G_{2})\). We complete the proof by showing that any canonical \(k\)-colouring of \(G_{1}\cup G_{2}\) can be transformed into \(c\) by a finite number of steps corresponding to edges in \(\operatorname{Can}_{k}^{\pi}(G_{1}\cup G_{2})\). Suppose a canonical \(k\)-colouring \(d\) of \(G_{1}\cup G_{2}\) is given. Let \(M\) be the largest colour which \(d\) assigns to a vertex of \(G_{1}\). Let \(H_{2}\) be the subgraph of \(G_{2}\) induced by the set of vertices on which colours \(1,2,\ldots,M\) appear. Since \(M\geq\chi(G_{1})\geq 1+col(G_{2})\geq 1+col(H_{2})\), the (ordinary) \(M\)-colouring graph of \(H_{2}\) is connected [6; 9]. Hence there is a sequence of steps corresponding to edges in \(\operatorname{Can}_{k}^{\pi}(G_{1}\cup G_{2})\) that transforms \(d\) to a canonical colouring \(d^{\prime}\) which agrees with \(c_{2}\) on \(V(H_{2})\). The following step can then be repeated until \(d^{\prime}\) is transformed into a canonical colouring that agrees with \(c_{2}\) on \(V(G_{2})\).