Prove that if $G$ is a tree, then $G^3$ is Hamiltonian.

Question

The graph $G^n$ is a graph obtained by connecting every pair of vertices $a,b$ in $G$ with $d(a,b) \le n$. Prove that if $G$ is a tree, then $G^3$ is Hamiltonian.

If $G$ is tree and $G^n$ is Hamiltonian connected, then $G^3$ is Hamiltonian connected. Hence it is sufficient to prove that the cube of every tree is Hamiltonian connected. If we show this with small values of $n$ the result is obvious and $G^2$ is not Hamiltonian.

How to prove this question ?

Answer 1

See: Karaganis, J. J., On the cube of a graph, Canad. Math. Bull. 11, 295-296 (1968).

Answer 2

We prove the result using a simplified version of the proof from "On the cube of a graph" by Karaganis (which actually proves a stronger result that $G^3$ is Hamiltonian connected, i.e. that any two vertices has a Hamiltonian path between them, though we won't do so here).

Lemma: For any edge $(u,v)$ in a tree $T$, there is a Hamiltonian path from $u$ to $v$ in $T^3$.

Proof:

For a 2 or 3-vertex tree, the result is obvious. When the tree has more than 3 vertices, proceed by induction: cut the $(u,w)$ edge and obtain two smaller trees, $T_u$ which includes $u$ and $T_w$ which includes $w$.

Let $u_1$ be adjacent to $u$ in $T_u$ (without loss of generality, $u_1$ exists because $T$ has more than 3 vertices). By inductive hypothesis, there's a Hamiltonian path $P_u$ of $T_u$ from $u$ to $u_1$. Also, since $u$ is adjacent to $w$ in $T$, the distance between $u_1$ and $w$ is at most 2, and thus $T^3$ includes the edge $(u_1,w)$. Similarly, if $T_w$ contains other vertices, then $T^3$ also contains the edge $(u_1, w_1)$ for any edge $w_1$ that is adjacent to $w$ in $T_w$, and by induction there's also a Hamiltonian path $P_w$ of $T_w$ from $w_1$ to $w$.

Hence, a Hamiltonian path of $T^3$ always exists by taking the path $P_u$, and then either taking the edge $(u_1, w)$ if $T_w$ only contains $w$ or taking the edge $(u_1, w_1)$ and then the path $P_w$.

Theorem: Let $G$ be a connected graph. Then $G^3$ has a Hamiltonian cycle.

Proof:

Compute any spanning tree of $G$ and take any edge $(u,w)$. The Lemma guarantees that there will be a Hamiltonian path from $u$ to $w$. Add the edge to the path and you have a Hamiltonian cycle.