Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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"? –  joriki Feb 27 '12 at 23:44
    
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. –  Henry Feb 27 '12 at 23:47
    
@joriki Yes, I definitely meant "at least". Thanks for pointing that out. –  user825089 Feb 27 '12 at 23:47
    
@Henry yes, you are right, forgot about that case. –  user825089 Feb 27 '12 at 23:51
    
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. –  Arthur Feb 28 '12 at 0:10

2 Answers 2

up vote 4 down vote accepted

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.)

share|improve this answer
2  
You should probably fix that to say that every connected graph has a spanning tree, or that every graph has a spanning forest. –  Brian M. Scott Feb 28 '12 at 0:35
    
@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. –  user825089 Feb 28 '12 at 0:49
    
And I am definitely accepting this! Thank you so much! –  user825089 Feb 28 '12 at 0:59
    
@user825089: Yes, your reasoning here is fine. –  Brian M. Scott Feb 28 '12 at 5:07
    
@BrianM.Scott: you're right, I've fixed it. (The original problem has the connected hypothesis. But I still shouldn't lie!) –  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-v$, 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.