Given a connected graph $G$, define $G^2$ to be a graph with same vertex set as $G$ and edge between two vertices $u$ and $v$ iff the distance between $u$ and $v$ in $G$ is at most $2$.
Is it true that $G^2$ is always hamiltonian?
I think that I've proved it, but since I am asked to prove the corresponding result for $G^3$ instead of $G^2$, I doubt that this result is true. If it is not true, can you please give a counter example?
Any tree in which there is a vertex connected to at least $3$ non-leafs is a counterexample.
Assume there is a Hamiltonian cycle starting at $v$ and let $\ell_1$ and $\ell_2$ be the first two non-leaf neighbours of $v$ in the cycle, in that order. Notice that the Hamiltonian cycle must be like this: $v,\dots, \ell_1,\color{red}{\dots} \ell_2,\dots$. However the problem is that after $\ell_2$ it is no longer possible to cross over $v$ and reach the other neighbours of $v$.
(The red dots $\color{red}{\dots}$ may be a (possibly empty) sequence of leafs that are connected to $v$, I hadn't noticed it initially).
If you want a concrete example I suggest you consider the following graph: