# Prove that if a graph is Hamiltonian then after removing k vertices, number of its connected components increases to no more than k.

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.

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