## 5 Can\({}_{k}^{\pi}(T_{2n,n})\)
We now show that, for any such sequence \(\pi\), the graph \(\mathrm{Can}_{2n}^{\pi}(T_{2n,n})\) is a tree. According to the discussion above, the vertices of \(\mathrm{Can}_{2n}^{\pi}(T_{2n,n})\) can be taken to be the binary sequences of length \(n\), with two sequences being adjacent if and only if they differ in exactly one position, and all entries to the right of that position are zero. Since any binary sequence can be reached from \(00\ldots 0\) by introducing 1s from left to right, the graph \(\mathrm{Can}_{2n}^{\pi}(T_{2n,n})\) is connected. The proof is complete once we show that the sum of the vertex degrees equals \(2(2^{n}-1)\). The degree of \(00\ldots 0\) is \(n\). Any other binary sequence contains at least one \(1\). If the rightmost \(1\) is in position \(i\) then the degree of \(b_{1}b_{2}\cdots b_{n}\) is \(n-i+1\) and the number of such sequences is \(2^{i-1}\). Hence, the sum of the vertex degrees is  
\[n+\sum_{i=1}^{n}2^{i-1}(n-i+1) = n+(n+1)\sum_{i=1}^{n}2^{i-1}-\sum_{i=1}^{n}2^{i-1}i\] \[= n+(n+1)(2^{n}-1)-\left((n+1)2^{n}-(2^{n+1}-1)\right)\] \[= 2\cdot 2^{n}-2.\]  
Since the description of \(\mathrm{Can}_{2n}^{\pi}(T_{2n,n})\) uses no properties of \(\pi\) other than that the subgraph of \(T_{2n,n}\) induced by the first \(n\) vertices of \(\pi\) is complete, it is clear that any two trees arising from such sequences are isomorphic. This can also be proved by induction on \(n\) by using the observation that the subtree induced by the set of sequences in which the first entry is \(0\) is isomorphic to \(\mathrm{Can}_{2(n-1)}^{\pi}(T_{2(n-1),n-1})\), as is the subtree induced by the set of sequences in which the first entry is \(1\). The argument above shows that, for \(n>1\), the leaves of \(\mathrm{Can}_{2n}^{\pi}(T_{2n,n})\) correspond to precisely the binary sequences in which \(b_{n}=1\). Thus, \(\mathrm{Can}_{2n}^{\pi}(T_{2n,n})\) has exactly \(2^{n-1}\geq 2\) leaves, and hence never has a Hamilton cycle. There is a Hamilton path only when \(n\leq 2\) (recall that \(T_{2,1}\cong\overline{K}_{2}\), and \(T_{4,2}\cong K_{2,2}\cong C_{4}\)). For an ordering \(\pi\) such that the subgraph induced by the first \(n\) vertices is complete, the tree \(\mathrm{Can}_{6}^{\pi}(T_{6,3})\) is shown in Figure 4. For any such ordering, the tree \(\mathrm{Can}_{6}^{\pi}(T_{8,4})\) is constructed from two copies of this tree, one arising from concatenating a \(1\) on the left of each sequence and the other arising from concatenating a \(0\) on the left of each sequence, and then joining the vertices \(0000\) and \(1000\). It remains to consider the graphs \(\mathrm{Can}_{k}^{\pi}(T_{2n,n})\) for \(n<k<2n\) and sequences \(\pi\) for which the first \(n\) vertices is complete. **Proposition 6**. : _Let \(n\geq 1\) and \(n<k<2n\). If the subgraph of \(T_{2n,n}\) induced by the first \(n\) vertices in the sequence \(\pi\) is complete, then \(\mathrm{Can}_{k}^{\pi}(T_{2n,n})\) is a tree on \(\binom{n-1}{t}+\binom{n-1}{t-1}+\cdots+\binom{n-1}{0}\) vertices. Further, if the subgraph of \(T_{2n,n}\) induced by the first \(n\) vertices in the sequence \(\phi\) is complete, then \(\mathrm{Can}_{k}^{\pi}(T_{2n,n})\cong\mathrm{Can}_{2n}^{\phi}(T_{2n,n})\)._  
Figure 4: The tree \(\mathrm{Can}_{6}^{\pi}(T_{6,3})\)  
**Proof. ** Observe that \(\mathrm{Can}_{k}^{\pi}(T_{2n,n})\) is the subgraph of \(\mathrm{Can}_{2n}^{\pi}(T_{2n,n})\) induced by the sequences with at most \(t=k-n\) ones. There are \(\
u={n-1\choose k}+{n-1\choose k-1}+\cdots+{n-1\choose 0}\) such sequences. Hence \(\mathrm{Can}_{k}^{\pi}(T_{2n,n})\) has exactly \(\
u\) vertices. As before, since any binary sequence with at most \(t\) ones can be reached from \(00\ldots 0\) by introducing ones from left to right, the graph \(\mathrm{Can}_{k}^{\pi}(T_{2n,n})\) is connected, and therefore is a tree. In addition, as before, the description of \(\mathrm{Can}_{k}^{\pi}(T_{2n,n})\) uses no properties of \(\pi\) other than that of the subgraph of \(T_{2n,n}\) induced by the first \(n\) vertices of \(\pi\) is complete.