1
$\begingroup$

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!

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

Contradiction isn't the most natural way to do this, since there's a straightforward constructive proof.

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.")

$\endgroup$
  • $\begingroup$ So, in order for G' to have a Hamiltonian cycle, G has to have a path? That makes sense, since you can't have a cycle without a path (I think). And yeah, the contradiction would be strange, but pretty straightforward as you suggest. Guess I'm still trying to visualize this better. $\endgroup$ – flo_mar Oct 31 '18 at 16:58
  • $\begingroup$ 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. $\endgroup$ – David Richerby Oct 31 '18 at 17:36

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.