That every 5-vertex path in the dodecahedron lies in a Hamiltonian cycle?

Question

In this problem ,it occurred to me that erasing the vertices that are between the trajectory, it only remains to show that there is a Hamiltonian path from the first to the last vertex of the trajectory. But I stagnate in that step.

Answer 1

(Disclaimer: algebraic graph theory is not my thing, so take this answer with some salt).

Given a path $P: u_1, u_2, u_3, u_4, u_5$ in the dodecahedron $G$, you want to show that there is a $u_1-u_5$ hamiltonian path in $G-\{u_2, u_3, u_4\}$.

If you try removing the three vertices of a length 2 path, you'll notice the graphs look rather similar. The key here is symmetry.

In particular, any 3-vertex path (such as our u_2, u_3, u_4 path) lies entirely on the boundary of a unique face, and such a path is uniquely determined by just picking both a face, and the middle vertex of the path on that face. (For our example, u_3 is the middle vertex). The important symmetry features of the dodecahedron are thus:

• If $f_1$ and $f_2$ are two faces of $G$, there is an automorphism (symmetry) carrying $f_1$ to $f_2$.
• 'Rotating' any face is a symmetry of $G$.

In particular, if $u_2, u_3, u_4$ and $x_2, x_3, x_4$ are the middle parts of two different paths, then there are faces $f_u$ and $f_x$ that these middle parts lie on. There is an automorphism $\varphi$ of the dodecahedron carrying $f_u$ to $f_x$, and another one $\sigma$ that rotates the path segment $\varphi(u_2, u_3, u_4)$ onto the path $x_2, x_3, x_4$. So it doesn't actually matter what path $P$ you chose, removing the middle three vertices leaves you with the same graph! (up to isomorphism) This means you only need to find the Hamiltonian path after deleting one set of 3 vertices, and all the other possibilities come along for free.

We have to be a little careful, because after deleting the three vertices, there are still a couple of possible 5-vertex paths that could have those 3 vertices in the middle.

I'll leave it to you to check that if $v_1$ is adjacent to $u_2$, and $v_5$ is adjacent to $u_4$, that there is a $v_1-v_5$ hamiltonian path in $G-\{u_2, u_3, u_4\}$ (for any fixed choice of $u_2, u_3, u_4$ you like). By our symmetry argument above, doing this completes the proof.