# Deleting a vertex from a Hamiltonian graph

Let $G=(V,E)$ be a connected simple graph with vertex $v\in V$. Define $G'=(V',E')$ with $V'=V\smallsetminus{v}$ and $E'=\{e\in E|v\not\in e\}$. Prove that if $G$ is Hamiltonian then there exists a Hamiltonian path in $G'$.

Progress:
Assume that $G'$ doesn't have a Hamiltonian path. This implies that $G'$ isn't Hamiltonian either. There are a few cases:
1) $G'$ is not connected. Add $v$ and all the deleted edges back. In order for the new graph $(G)$ to be Hamiltonian there must exists a Hamiltonian cycle. However $v$ gets visited at least twice.
2) $G'$ contains a subdivision of $K_{3,3}$ or $K_5$ which implies that it'd be impossible to retrieve $G$.

We get a contradiction in both cases.

I'm not quite sure about this proof. It seems like a direct proof would be much more elegant.

• In part 2) you're saying $G'$ is not planar. That has nothing at all to do with the problem, so far as I can see. This problem is trivial. You are overthinking it. – saulspatz Mar 13 '18 at 18:47
• Would it be correct to say that if $(v_0,v_1,...,x,v,y,...,v_n=v_0)$ is a Hamiltonian cycle in $G$ then $(y,...,v_0,v_1,...,x)$ is a Hamiltonian path in $G'$? – Slavik Egorov Mar 13 '18 at 19:01
• That's it exactly. – saulspatz Mar 13 '18 at 19:28

When you delete $v$, a Hamiltonian cycle in $G$ becomes a Hamiltonian path in $G’$.