Prove that if a graph $G$ has a Hamilton path, then for every $S\subseteq V(G)$, the number of components of $G-S$ is at most $|S|+1$.

Question

Prove that if a graph $G$ has a Hamilton path, then for every $S\subseteq V(G)$, the number of components of $G-S$ is at most $|S|+1$.

My solution (rough and incorrect): Consider a Hamilton path $P$ in $G$. $P$ has to visit each of the components of $G-S$. There is no direct path between two components so the path $P$ has to go to $S$ when it leaves a component. So the number of components in $G-S$ is at most $|S|$.

This is obviously incorrect. What am I missing here? How would it be $|S|+1$ and not $|S|$. Also how can I show that the arrival vertices are distinct? Surely if you prove it this way, you could have just, for example, one vertex in $S$ which has an edge connecting to all of the components.

Answer 1

For your first point: In a Hamilton path, how many components does the path actually have to leave?

For your second point: If the path is repeatedly visiting the same vertex, as in your example, would it really be a Hamilton path?

Answer 2

I would try with induction.

Deleting single vertex $v$ from $S$ the graph breaks in to at most $2$ components $G_1$ and $G_2$, since $v$ is on some Hamilton path. So deleting the rest of vertices from $S_1= S\cap G_1$ and $S_2=S\cap G_2$ we get at most $|S_1|+1$ and $|S_2|+1$ components (by induction assumption), so we have $$ |S_1|+1+|S_2|+1 = |S|-1+2 =|S|+1$$ components ($S= S_1\cup S_2\cup \{v\}$).