# Proof By Contradiction - Hamiltonian Paths and Cycles

Was hoping if anyone had any way to prove the following claim using proof by contradiction

Let $$G = (V, E)$$ be a simple graph with at least one vertex, and let $$G'$$ be the graph formed by adding a new vertex $$v$$ and making it adjacent to every vertex in $$V$$.

Claim: $$G$$ has a Hamiltonian Path if and only if $$G'$$ has a Hamiltonian cycle.

I tried manipulating the definitions of each of the two (path vs. cycle), but didn't find much luck. Any thoughts?

Thanks!

• What prompted you to want a proof by contradiction for this, or at all? – Derek Elkins Oct 31 '18 at 18:32

Suppose $$G$$ has a Hamiltonian path. How can you extend that to a Hamiltonian cycle of $$G'$$? Conversely, suppose that $$G'$$ has a Hamiltonian cycle. Cover up $$v$$ with your finger – what do you see?
It's possible to rewrite the reasoning hinted at above as a proof by contradiction, but it's not very natural. ("Suppose $$G$$ has a Hamiltonian path but $$G'$$ has no Hamiltonian cycle. Oh, look, here's a Hamiltonian cycle in $$G'$$ – contradiction.")
• Yes -- a Ham cycle in $G'$ must visit every vertex of $G'$ and, if you forget about the new vertex $v$, then you're left with a path. – David Richerby Oct 31 '18 at 17:36