I'm trying to prove that any simple connected graph with at least $3$ vertices ($|V| \ge 3$) has at least $2$ vertices whose removal will not lead to the increment of number of components. In other words, there are at least $2$ vertices that are non-cut vertices.

Attempt at solution:

I tried to prove it using induction by the number of vertices: $n - t \ge 2$, where $n$ is the number of vertices our graph has, and $t$ is a number of cut vertices.

  1. Base
    Let $n =3$, then the graph will look like this: $О-О-О$
    Clearly, it has one cut vertex (the middle one). So, $3-1 \ge 2$ holds.
    Or it can be a full graph, then $3 - 0 \ge 2$ also holds.

  2. Assumption
    Let $n = k$, and the formula holds, $k - t >= 2$

  3. Step
    Prove for $n = k + 1$
    If we add one vertex to the graph, it could either be a cut vertex or non-cut vertex. In case it is a cut vertex, we have
    $$\begin{align*}&(k+1) - (t+1) \ge 2\\ &k + 1 - t - t\ge 2\\ &k\ge 2\end{align*}$$

In case it is not a cut vertex...and I'm stuck here, because anything can happen. The number of cut vertices might increase, might decrease, or stay the same.

I'm sure there is better and shorter proof to this, and I really hope someone could help me.

  • $\begingroup$ Your first sentence is contradictory; the formula allows $|V|=3$ whereas the wording doesn't. From your attempt at a solution, it seems that you meant "at least $3$ vertices"? $\endgroup$ – joriki Feb 27 '12 at 23:44
  • $\begingroup$ If you take this route, then your step 1 also needs to take into account the possibility that the graph has all three vertices connected to each other. $\endgroup$ – Henry Feb 27 '12 at 23:47
  • $\begingroup$ @joriki Yes, I definitely meant "at least". Thanks for pointing that out. $\endgroup$ – ivt Feb 27 '12 at 23:47
  • $\begingroup$ @Henry yes, you are right, forgot about that case. $\endgroup$ – ivt Feb 27 '12 at 23:51
  • $\begingroup$ In the induction step, assume that there are only cut-vertices. Choose one, remove it. Now there should be at most one non-cut vertex in each connected component of the resulting graph (the one connected to the removed vertex), but this contradicts the induction assumption. You're going to have to work a bit on this, because the resulting subgraphs could be too small. $\endgroup$ – Arthur Feb 28 '12 at 0:10

I think the result follows from the fact that every connected graph has a spanning tree and every tree with more than one vertex has at least two leaves.

(By the way, if you want to prove this by induction on $k$, then in Step 3 you shouldn't start with a $k$-vertex graph and add a vertex to it. You're trying to prove some property of $(k+1)$-vertex graphs, so you need to start with a $(k+1)$-vertex graph; then you might choose to take one vertex away and use the induction hypothesis.)

  • 2
    $\begingroup$ You should probably fix that to say that every connected graph has a spanning tree, or that every graph has a spanning forest. $\endgroup$ – Brian M. Scott Feb 28 '12 at 0:35
  • $\begingroup$ @Greg Martin That is a great idea! I decided to abandon my induction method in favor of this. Could someone please check my reasoning: Every connected graph can be reduced to a tree by deleting certain edges until the circuit rank reaches 0. Since |V|>=3 was a requirement, the resulting tree will have at least 3 vertices. Since every tree with |V|>1 has at least two terminal vertices, the original graph must also have at least two terminal vertices. $\endgroup$ – ivt Feb 28 '12 at 0:49
  • $\begingroup$ And I am definitely accepting this! Thank you so much! $\endgroup$ – ivt Feb 28 '12 at 0:59
  • $\begingroup$ @user825089: Yes, your reasoning here is fine. $\endgroup$ – Brian M. Scott Feb 28 '12 at 5:07
  • $\begingroup$ @BrianM.Scott: you're right, I've fixed it. (The original problem has the connected hypothesis. But I still shouldn't lie!) $\endgroup$ – Greg Martin Feb 28 '12 at 7:26

Let $G$ be a connected graph of order 3 or more, and let $u$ and $v$ be two vertices of $G$ whose distance from one another, $l$, is equal to the diameter of $G$, $d(u,v) = diam(G)=l$. We claim that neither $u$ nor $v$ are cut-vertices of $G$.

Assume, to the contrary, that one of $u$ and $v$, say $u$, is a cut-vertex of $G$. Then, in $G-u$, there is a vertex $x$ in a different component from $v$. Thus, in $G$, $u$ lies on every $v-x$ path.

Now, let $P$ be a shortest $v-x$ path in $G$. Since $P$ contains $u$, $d(v, x) > d(v,u)$ which is impossible.


This is an argument in Douglas West's Introduction to Graph Theory (with very slight comments on my part.)

Let $G$ be a simple graph (West assumes $G$ is a graph with a non-loop edge). Then there is some maximal path $P$ in $G$ with end point $u$. Note that all neighbors of $u$ must lie on $P$, otherwise if $u$ has some neighbor not on $P$, then we could extend $P$, but $P$ is maximal. So $P-u$ is connected in $G-u$ and all the neighbors of $u$ still lie on $P-u$ (that is, there is still a path between any $2$ of $u$'s neighbors), so $G-u$ is connected. Since $P$ has $2$ endpoints, $G$ has at least $2$ non-cut-vertices.

  • $\begingroup$ how does West use the fact that G contains a non-loop edge? it seems the maximal path in G isn't even guaranteed to use the 1 guaranteed non loop edge, $\endgroup$ – H_1317 Jan 23 at 7:25
  • $\begingroup$ nevermind, if all we had was a loop as our graph, the number of components go from 1 to 0 $\endgroup$ – H_1317 Jan 23 at 7:28
  • $\begingroup$ @H_1317 Right, West tends to make assumptions that take care of some weird edge case(s) but never uses the assumptions explicitly. I should've mentioned that, thanks. $\endgroup$ – Hendrix Jan 24 at 17:58

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.