1
$\begingroup$

If $G = (V, E)$ is a simple graph with at least one vertex and $G'$ is the graph formed by adding a new vertex $v$ and making it adjacent to every vertex in $V$. How do you show that $G$ has a Hamiltonian path if and only if $G'$ has a Hamiltonian cycle?

If you have a Hamiltonian cycle that means that every vertex is traversed at least once where the graph is linked back to the starting point without backtracking. If the Hamiltonian cycle exists in $G'$ then the exclusion of the $v$ vertex would turn the Hamiltonian cycle into a Hamiltonian path. However, I don't understand how you would prove that using induction or contradiction.

$\endgroup$
  • $\begingroup$ What do you think about the problem? $\endgroup$ – Parcly Taxel Nov 1 '18 at 1:38
  • $\begingroup$ If you have a Hamiltonian cycle that means that every vertex is traversed at least once where the graph is linked back to the starting point without backtracking. If the Hamiltonian cycle exists in G' then the exclusion of the v vertex would turn the Hamiltonian cycle into a Hamiltonian path. However, I don't understand how you would prove that using induction or contradiction. $\endgroup$ – Ramon Nov 1 '18 at 1:51
  • $\begingroup$ @Ramon You mean "... every vertex is traversd exactly once"? $\endgroup$ – Hagen von Eitzen Nov 1 '18 at 1:58
  • $\begingroup$ Why do you specifically want to use induction or contradiction? $\endgroup$ – Hagen von Eitzen Nov 1 '18 at 1:59
  • $\begingroup$ Yes. That is what I mean. Thank you for the correction. I believe that induction would be the best way to approach this situation. $\endgroup$ – Ramon Nov 1 '18 at 2:04
1
$\begingroup$

Suppose $G$ has a Hamiltonian path. By adding the vertex $v$ that turns $G$ into $G'$, then adding edges from $v$ to the path's ends, the path turns into a Hamiltonian cycle of $G'$. Conversely, any Hamiltonian cycle of $G'$ can be broken into a path by removing the two edges incident to $v$, and the result is a Hamiltonian path on $G$.

$\endgroup$

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.