2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user499701 Feb 4 at 21:04
  • $\begingroup$ 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? $\endgroup$ – user499701 Feb 4 at 21:10
  • $\begingroup$ @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? $\endgroup$ – Gregory J. Puleo Feb 4 at 23:10
  • $\begingroup$ 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? $\endgroup$ – user499701 Feb 5 at 0:27
  • $\begingroup$ @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. $\endgroup$ – Gregory J. Puleo Feb 5 at 0:49
1
$\begingroup$

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

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