Identifying Cut-Vertices

Introducing cut-vertices

A cut-vertex of a connected graph is a vertex whose removal results in disconnecting the graph.

For example, the labeled vertex in each of the following examples is a cut-vertex because removing it creates two, three, and five components, respectively.

Removing a cut-vertex from a connected graph breaks it into components because all paths of the original graph from vertices of one of these components to vertices of another component pass through that cut-vertex.

In the context of a communication network, failure at a cut-vertex would imply that certain parts of the network become isolated from other parts. Identification of cut-vertices can help in identifying the vulnerabilities as well as communication bottlenecks in a network.

When is the root a cut-vertex?

Let’s say a graph $G$ has a depth-first tree with the root vertex having two or more children. Consider the subtrees rooted at the children of the root vertex.

As there are no cross-edges in an undirected graph, all paths of $G$ between any two vertices belonging to these different subtrees must pass through the root. So, a root with two or more children is a cut-vertex. On the other hand, a root with at most one child is not a cut-vertex since removing it would not disconnect the graph.

Conclusion I: The root of a depth-first tree of a graph $G$ is a cut-vertex of $G$ if and only if it has at least two children.

We just saw how to tell if a root vertex is a cut-vertex. But what about the other vertices of the graph?

When is a non-root vertex a cut-vertex?

Let’s think about this. Suppose $v$ is not a root of a depth-first tree. If there is no back-edge from a descendant $u$ of $v$ to an ancestor $w$ of $v$, then all paths in the graph between $u$ and $w$ must go through the vertex $v$. Removal of $v$ from the graph would end up with $u$ and $w$ landing in different components, making $v$ a cut-vertex.

We just proved the following:

For a non-root vertex $v$, if there is no back-edge from a descendant of $v$ to an ancestor of $v$, then $v$ is a cut-vertex.

Example: The vertex ...