## 3 Unions and Joins
If the current colouring does not agree with \(c_{2}\) on \(V(G_{2})\), then let \(x\) be the last vertex of \(G_{2}\) which is not coloured \(c_{2}(x)\), and recolour \(x\) with \(c_{2}(x)\) (Note that any the colour of any such \(x\) is greater than \(M\)). The resulting colouring is proper because of the recolouring of \(H_{2}\) done earlier, and canonical by the maximality of the position of \(x\). Finally, since \(\operatorname{Can}_{k}^{\phi}(G_{1})\) is connected and \(\chi(G_{1})\geq\chi(G_{2})\), the subgraph of \(\operatorname{Can}_{k}^{\pi}(G_{1}\cup G_{2})\) induced by the set of (canonical) colourings for which the restriction to \(V(G_{2})\) is \(c_{2}\) is isomorphic to \(\operatorname{Can}_{k}^{\phi}(G_{1})\), and is therefore connected. Hence there is a sequence of steps corresponding to edges in \(\operatorname{Can}_{k}^{\pi}(G_{1}\cup G_{2})\) that transforms a canonical colouring which agrees with \(c_{2}\) on \(V(G_{2})\) into \(c\). This completes the proof. The hypothesis of the above theorem can be relaxed slightly to \(\chi(G_{1})\geq 1+c_{0}(G_{2})\), where \(c_{0}\) is the least integer such that \(k\)-colouring graph of \(G\) is connected for all \(k\geq c_{0}\). By the result of [6], \(c_{0}(G_{2})\leq col(G_{2})\). Corollary 4: _Let \(k,n\geq 1\) and \(G\) be a graph with at least one edge. If there exists a vertex ordering \(\pi\) such that \(\operatorname{Can}_{k}^{\pi^{\prime}}(G)\) is connected, then there exists an order \(\pi^{\prime}\) for which \(\operatorname{Can}_{k}^{\pi^{\prime}}(G\cup\overline{K}_{n})\) is connected._  
Proof: The colouring number of \(K_{1}\) equals \(1\). Apply Theorem 4.1 inductively. We conclude this section by considering the join operation. Observe that in any colouring of \(G_{1}\lor G_{2}\), the set of colours that appear on the vertices of \(G_{1}\) is disjoint from the set of colours that appear on the vertices of \(G_{2}\). With this observation, the proof of the first proposition below is straightforward, and hence is omitted. Proposition 4: _Let \(\pi\) be a vertex ordering of the graph \(G\). If \(\pi^{\prime}\) is the vertex ordering obtained by inserting the vertices of the \(K_{r}\) at the beginning of \(\pi\), then \(\operatorname{Can}_{l}^{\pi}(G)\cong\operatorname{Can}_{l+r}^{\pi^{\prime}}(G \lor K_{r})\)._  
Corollary 5: _If \(\operatorname{Can}_{l}^{\pi}(G)\) is connected (resp. has a Hamilton path, has a Hamilton cycle) then there exists an order \(\pi^{\prime}\) such that \(\operatorname{Can}_{l+r}^{\pi^{\prime}}(G\lor K_{r})\) is connected (resp. has a Hamilton path, has a Hamilton cycle)._  
In contrast, by Proposition 4.1, in almost any ordering \(\pi^{\prime}\) of the vertices that does not begin with all the vertices of \(K_{r}\) the corresponding \(\operatorname{Can}_{l+r}^{\pi^{\prime}}(G\lor K_{r})\) will be disconnected. **Corollary 5**: _Let \(T\) be a tree with at least three vertices, and \(k\geq 4\). For any integer \(n>1\), there exists a vertex ordering \(\pi^{\prime}\) such that \(\operatorname{Can}_{k+n}^{\pi^{\prime}}(T\lor K_{n})\) is Hamiltonian._  
For any such \(k\), there is a vertex ordering \(\pi\) such that \(\operatorname{Can}_{k}^{\pi}(T)\) is Hamiltonian [1]. The next corollary implies, among other things, that the canonical \(c\)-colouring graph of a wheel on \(n\) spokes is connected for all \(c\geq 4\). **Corollary 6**: _Let \(k\geq 4\), \(t\geq 3\) and \(n\geq 1\). There exists a vertex ordering \(\pi^{\prime}\) such that \(\operatorname{Can}_{k+n}^{\pi^{\prime}}(C_{t}\lor K_{n})\) is connected._  
For any such \(k\), there is a vertex ordering \(\pi\) such that \(\operatorname{Can}_{k}^{\pi}(C_{t})\) is connected [1]. **Proposition 3**: _Let \(k,n\geq 1\). Suppose there exists a vertex ordering \(\pi\) such that \(\operatorname{Can}_{k}^{\pi}(G)\) is connected.