Let be a connected simple undirected graph with a set of vertices and a set of edges, let be a spanning tree of rooted at a vertex , and let be a numbering on , where we assume that the following conditions (a) and (b) hold.
(a) For each edge , vertex is either an ancestor or a descendant of in .
(b) For each vertex and the parent of in , .
Let denote the set of leaves in . For each vertex , let denote the set of neighbors of in , and let denote the set consisting of vertex and the descendants of in . Define a function
such that
Answer the following questions.
(i) Prove that no leaf is a cut-vertex in .
(ii) Prove that a necessary and sufficient condition for the root to be a cut-vertex in is that has at least two children in .
(iii) Prove that a necessary and sufficient condition for a vertex to be a cut-vertex in is that has a child in such that
If has only one child in , i.e., is a leaf vertex of , then by the same argument of (1), we know that is still connected.
This contradicts the assumption taht is a cut-vertex.
(Sufficiency) Assume that has at least two children in . Let two of them be and .
Consider the two subtrees and .
Since and are different children of the root , the vertices in and are not in an ancestor-descendant relationship with each other.
By condition (a), there cannot be any edge between a vertex in and a vertex in .
After deleting , the two subtrees and cannot be connected to each other.
Hence is disconnected, which implies that is a cut-vertex.
We prove that there must exist a child of such that by contradiction.
Suppose that every child of satisfies .
Then for each child of , there exist some vertex and some neighbor such that .
Since , the vertex is a descendant of . By condition (b), every descendant of has numbering greater than .
Therefore, the vertex of is not in .
By condition (a), since is a descendant of , and y has numbering smaller than , the vertex must be a proper ancestor of .
Thus every child subtree of has an edge to some proper ancestor of , i.e., after deleting , every child subtree can still connect to the part above through an edge to a proper ancestor of .
Therefore, remains connected, which contradicts the assumption that is a cut-vertex.
(Sufficiency) Assume that has a child satisfying .
Note that is a neighbor of , i.e., , when computing , the vertex can be reached from by one graph edge.
Hence , together with the assumption we have
This means that the subtree cannot reach any proper ancestor of through a graph edge. The smallest numbered vertex reachable from is exactly .
Equivalently, has no edge to any proper ancestor of .
After deleting , the subtree is disconnected from the part of the graph above . Therefore is disconnected.