Let $G = (V, E)$ be a Hamiltonian graph and $A \subseteq V$. Prove that the graph obtained from $G$ by removing all the vertices in $A$ has at most $|A|$ connected components.

This seems a bit counter-intuitive to me. How can removing $|A|$ vertices can produce a graph with $|A|$ of connected components? Any ideas?


Note that this proposition can be false if $G$ is not hamiltonian. Consider a star with $n$ vertices. If you remove the center, you are left with $n-1$ connected components (the isolated vertices).

Consider first a graph $G$ which is a cycle $C$ (then it is a hamiltonian graph). If you remove $A$ from $C$, the worse case scenario is that none of the vertices in $A$ is adjacent in $C$. In this case, you can check that removing $A$ from $C$ leaves $\vert A\vert$ connected components. You can prove this formally using induction. To get the idea, think for instance in a cycle with 4 vertices, what happens if you remove 2 nonadjacent vertices? and if you remove 2 adjacent vertices? or if you remove 3 vertices? or 1? or 4?

Now, if $G$ is a hamiltonian graph, it contains a cycle $C$ which has all the vertices. If you remove $A$ from $G$, we already know $C$ has at most $\vert A\vert$ connected components. Since there may be edges in $G-A$ between those components of $C-A$, the graph $G-A$ can only have less or equal connected components than the cycle $C-A$.

  • $\begingroup$ Yes, but what happens for a simple graphs, like square for example. It is Hamiltonian, but if we remove a vertex, we are left with a disconnected graph. $\endgroup$
    – user72151
    Oct 28 '15 at 16:15
  • $\begingroup$ I disagree. If we remove a vertex from the square, we are left with a connected graph. For instance, the square can be seen as a cycle $v_1v_2,v_2v_3,v_3v_4,v_4v_1$. If you remove, say, $v_1$, you can still go from $v_2$ to $v_3$, (using $v_2v_3$) and to $v_4$ (using the path $v_2v_3,v_3v_4)$. From $v_4$ you can also go back to $v_2$ with the same path. $\endgroup$
    – Nate River
    Oct 28 '15 at 16:20
  • $\begingroup$ Yes, now I see. I was thinking about the connected components. And I imaged the square as one connected component, and then clearly removing and edge will remove it from being a connected component. But, we are talking just paths, which can go both ways. Thanks for the clarification. $\endgroup$
    – user72151
    Oct 28 '15 at 16:29
  • 1
    $\begingroup$ I would like to point out that removing an edge from the square leaves it connected, so the resulting graph still has one connected component. The connected components need not have cycles. $\endgroup$
    – Nate River
    Oct 28 '15 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy