Maximum and minimum number of articulation points in a graph with $n$ nodes

4.5k Views Asked by At

What's the maximum and minimum number of articulation points in a graph with $n$ nodes?

I think the maximum is $n-2$ because the graph would be a straight line, and the nodes at the two ends can't be articulation points because they don't have children.

I think the minimum is $0$ because you can have a complete graph and if you remove any of the nodes the rest of the nodes are still connected.

However I can't prove that my answer is correct.

What's the correct answer and how do you prove it?

1

There are 1 best solutions below

2
On BEST ANSWER

You are almost done, your results are fine (except that you need to make a trivial exception for $n=1$). You have already shown that the maximum is at least $n-2$.

To prove that the maximum is at most $n-2$, we show that every graph has at least two vertices that are NOT articulation points.

This follows from three observations:

1) An isolated vertex is never an articulation point.

2) A connected graph with at least two vertices has at least 2 vertices that are not articulation points

3) The number of non-articulation points in a disconnected graph equals the sum of the number of non-articulation points in its components.

Only the second item requires some justification, the others are obvious.

For the second item we recall the facts that every connected graph has a spanning tree, that a leaf in a tree is never an articulation point (for the tree), and that a tree with at least two vertices has at least two leaves. So a spanning tree has at least two vertices that are not articulation points(for the tree, so certainly not for the entire graph).