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.
Best Answer
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$.