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

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.

## 2 Answers

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?

• Surely it would have to leave all the components. I understand it is different from a cycle, just can't see it, could you clarify? – user499701 Feb 4 at 21:04
• Also, maybe not repeatedly visiting the same vertex but how about if the path leaves a component, arrives at a vertex in $S$ and leaves the same vertex to another component? – user499701 Feb 4 at 21:10
• @user499701 Sure, it can arrive at a vertex in S and then immediately leave to another component, but if we're only keeping track of the times the path leaves a component (by entering S), then there's no double-count, because we didn't even try to count the time we exited S to reach the next component. To illustrate the point about "leaving all components", let's look at a silly example: the path on 3 vertices. Surely that graph has a Hamiltonian path. If S consists of just the vertex of degree 2, what can you say about the behavior of the Hamiltonian path regarding the components of G−S? – Gregory J. Puleo Feb 4 at 23:10
• Ahh, so in the case that both of the endpoints of the path are in $G-S$, the path would have to leave at most $|S|+1$ components? Is this all I have to add to my proof? – user499701 Feb 5 at 0:27
• @user499701 it's probably worth putting in an explicit explanation of where the $+1$ came from and why you're guaranteed to never repeat a vertex in $S$, but I think the overall structure of your proof looks OK. – Gregory J. Puleo Feb 5 at 0:49

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