For all graphs $G$, if $G$ is semi-Hamiltonian (contains a Hamilton path, i.e., a path that visits every vertex in $G$), then removing any $k$ vertices results in a graph with at most $k+1$ connected components.

Here is my solution.

$\textit{Proof.}$ Assume $G$ is semi-Hamiltonian. Then $G$ contains a path that visits every vertex in $G$. Thus, $G$ is connected. Pick $k$ vertices in $G$. If none of the $k$ vertices are bridges (That is, vertices whose removal results in a disconnected graph), then $G$ contains only 1 connected component, itself.

If all of the $k$ vertices are bridges, then if we remove the first we get $2$ connected components, then we remove the next vertex to get $3$ connected components and so on until we have removed all $k$ vertices and then have $k+1$ connected components.

If $m < k$ of the vertices were bridges then we will have $m+1 < k+1$ connected components.

To me this sounds fine but could anyone say if this sounds good or not to see if I make any leaps that were not able to be made? Thanks very much I appreciate it!


1 Answer 1


I don't see anywhere that you make essential use of the fact that $G$ has a Hamiltonian path. All mention of this property seems to be left behind once you establish the (much weaker) fact that $G$ is connected.

There is already a problem (a few, really) with your claim that if none of the $k$ vertices are "bridges" (the correct term is "cut vertex") then $G$ has only 1 component. You have already said that $G$ is connected so by definition $G$ has only 1 component!

In context, it is likely you meant to say that $G$ minus the $k$ vertices has 1 component, but that is not what you wrote. A reasonable reading of that sentence is that you claim if each vertex is not a cut vertex of $G$, then removing all $k$ of them at once leaves the graph connected. This is blatantly false, and if you believe it to be true, you should find an example to confirm it is false.

An alternative interpretation of the sentence is that you mean to remove one vertex at a time, in some particular order, until all $k$ are removed. If that is your intent, you have failed to convey this intent, because that is not how a reasonable reader will interpret the phrase "none of the $k$ vertices are bridges".

For the proof to be solid, somewhere past the first paragraph there needs to be logic that doesn't apply to the claw graph $K_{1,3}$ (one vertex adjacent to 3 other vertices). The result is false for this graph (which is fitting as it is not semi-Hamiltonian). However, I don't see any part of your reasoning that couldn't also be said for this graph, which tells me that somewhere in your reasoning is an unjustified claim.

  • 1
    $\begingroup$ Ok. Yes, I see that what I said doesn't really make any sense now that I read it again. What I meant was that if we have $k$ vertices in $G$ and none of them are cut vertices, then if we remove them we will still have a connected graph but I made a counterexample on paper and so I see this is false. I will work on this and come up with a better solution and edit my original post most likely tonight. Thanks for your reply. $\endgroup$
    – user43138
    Dec 16, 2012 at 4:36

You must log in to answer this question.