29.2.3. Articulation Points

In any simple graph G, if (G – v) is disconnected for every vertex v in the graph, then this implies that the graph G is also disconnected. This means that if every vertex v is an articulation point or cut vertex, then the graph G is disconnected.

An articulation point, or cut vertex, in a graph is a vertex that, when removed along with its incident edges, makes the graph disconnected. If every vertex in a graph is an articulation point, it follows that removing any single vertex will disconnect the graph. This establishes that if removing any vertex results in disconnection, then the graph itself must be disconnected.

Imagine a small town connected by roads. If every road leads to a main intersection (representing the articulation points), removing any one road would cause some parts of the town to become isolated. This illustrates how critical those roads are to the overall connectivity of the town, similar to how articulation points function in a graph.

If you take any connected simple graph, then there always exist at least two vertices, none of which is an articulation point.

In a connected graph, it can be shown that there are always at least two vertices that are not articulation points. This is proven by selecting the two vertices that are the farthest apart in the graph and showing that their removal does not disconnect the graph. Therefore, it suffices to assume that not all vertices can be articulation points in a connected graph with more than two vertices.

Think of a network of friends in a social circle. If you picture two friends who are on opposite sides of the circle, the removal of either friend doesn’t separate the entire group; the group remains connected through other friendships. This reflects how some vertices in a graph can be 'safe' from being articulation points.

The proof uses contradiction to show that if we assume one of the farthest vertices is a cut vertex, then it must lead to a scenario that contradicts our selection of the farthest vertices.

In this proof by contradiction, we start by selecting two vertices (u, v) as the farthest apart. If we assume one of them (say v) is a cut vertex, then its removal would disconnect the graph, which contradicts their selection as farthest apart since there would now be no path between u and v. Thus, both u and v must not be articulation points.

Imagine you’re in a maze. If you think you’ve found the exit but then learn that knocking down a wall leads you to the exit, you realize your path was never truly blocked. Similarly, the vertices assumed to be cut vertices don’t hinder connectivity as expected.

The question raised is whether we can have a simple connected graph where every vertex is a cut vertex, but based on previous claims, this is not possible.

The exploration reveals that while it may seem feasible for every vertex in a connected graph to be an articulation point, the earlier proof indicates that there must be at least two vertices that do not fulfill this role. Thus, no simple connected graph can have every vertex functioning as a cut vertex.

Consider a spider web: While each intersection point may seem critical to the overall integrity of the web, removing one segment doesn’t jeopardize the entire structure. Similar to the vertices in a graph, only some points need to be reinforced to maintain integrity.

--