1
$\begingroup$

I thought maybe induction? But components of a graph after removing k vertices aren't Hamiltonian and I'm not sure how to justify that removing one more vertix won't increase number of components by more than 1.

$\endgroup$
3
$\begingroup$

If you remove two vertices from a cycle, it will be cut into either one or two paths.

Each vertex you remove further, is in just one of those paths, and removing it cuts that path into at most two pieces (so removing $i$ additional vertices after the first two increases the number of components by at most $i$).

A Hamiltonian graph is just a cycle with some extra edges, and adding edges never increases the number of components.

$\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.