#Graph Theory Any Simple way to prove this ?

Question

A connected graph ‘G’ may have at most (n–2) cut vertices.

Comments

Take the exmple of k4 where n =4. In that we have n-2 =2 cut verties.

Answer 1

Cut vertices are those vertices whose removal disconnects the remaining graph.

Now when you have a connected graph of n vertices there are are two possibilities:

1. There are cycles involved

and

2. There are no cycles in the graph.

The worst case scenario for us to check is when there is no cycle involved, this means that the connectivity of entire graph is at the mercy of each vertex present.However In this case also the removal of any of the two end vertices will not disconnect the graph. example shown below.

Even if we remove A or E, the graph still remains connected. But if we try to remove any of B,C,D then the graph will surely get disconnected. So you can easily see that for this graph other than the two end vertices, every vertex is a cut vertex. Since this is an example of a minimally connected graph i.e, a tree hence it the maximum number of cut vertices that a graph can have.

therefore # of cut vertices in a graph are always <=n-2 where n is the number of edges.