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'$.

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.

  • $\begingroup$ 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. $\endgroup$ – saulspatz Mar 13 '18 at 18:47
  • $\begingroup$ 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'$? $\endgroup$ – Slavik Egorov Mar 13 '18 at 19:01
  • $\begingroup$ That's it exactly. $\endgroup$ – saulspatz Mar 13 '18 at 19:28

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.