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!

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

1 Answer 1

Reset to default
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.")

Improve this answer
$\endgroup$
2
  • $\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$
    – Omar Khan
    Oct 31, 2018 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, 2018 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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