Graph Theory – Proof That Any Simple Connected Graph Has at Least 2 Non-Cut Vertices

graph theory

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.

Best Answer

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

Related Question