In the Graph Theory lecture, there is a problem about the power of a graph and a hamiltonian cycle: For a simple graph $G$ and its vertex $x$, suppose that $G-x$ has at least tree non-trivial components in each of which $x$ has exactly one neighbor. Prove that the square of $G$ is not hamiltonian.
I tried to solve as follows: Let $C_1, C_2,$ and $C_3$ be components of $G-x$ and $w_i$ be a vertex in $C_i$ which is adjacent to $x$. Then each $w_i$ and $w_j$ are adjacent in $G^2$ for any distinct $1 \leq i, j \leq 3$. In addition, the unique vertex in $C_2$ which is adjacent to $w_1$ is $w_2$. Thus deleting $w_1$ disconnects $C_1$ and $C_2$, and so
$$\omega(G^2 – w_1) \geq 2 > 1 = \lvert \{w_1 \} \rvert$$
and so $G^2$ is not hamiltonian.
However, I realized that since $C_1$ is not trivial, each neighbors of $w_1$ in $C_1$ must be adjacent to $x$ in $G^2$, so deleting $w_1$ cannot disconnect the two components. I guess that deleting some of $w_1$, $w_2$ or $w_3$ can get the desired result, but it's hard to justify the statement. Could someone give me a hint?
Best Answer
I don't think I'll comment on your attempted proof, since I'm a bit unsure of some of the logic (including the mistake that you caught yourself). However, I'll give my own proof of this fact, which (I think) is quite straightforward:
Let $x$ be a vertex of $G$ such that $G - x$ has at least 3 nontrivial components in which $x$ has exactly one neighbor. Let $v_1, v_2$, and $v_3$ be the unique neighbors of $x$ in 3 such components $H_1, H_2$, and $H_3$ of $G - x$, and set $S$ = $\{x, v_1, v_2, v_3\}$. Since each $H_i$ $(i = 1, 2, 3)$ is nontrivial, $G^2 - S$ has at least 3 components. Within $S$, only $x$ and $v_i$ have neighbors in $H_i - v_i$ (both of the previous two claims follow from the definition of the square of a graph (think of distance considerations)). A spanning cycle of $G^2$ must therefore enter and exit $H_i - v_i$ via distinct vertices of $S$; these can only be $x$ and $v_i$, as established above. This forces at least 3 edges in such a cycle to be incident with $x$: one to each $H_i$. This, of course, is impossible in a Hamiltonian cycle; hence $G^2$ is not Hamiltonian.
Let me know if you'd like any clarifications.