From a Tree Branch to a Graph Component
Deleting an articulation point can split a connected graph into several pieces. The block-cut tree records how the graph’s blocks meet at articulation points, so removing the corresponding tree node exposes those pieces as branches. The key is to interpret each branch correctly: its block nodes describe connected portions of the original graph, but a block containing the deleted vertex must be read with that vertex removed.
Throughout, graphs are finite and simple. A graph is connected if every pair of its vertices is joined by a path. A vertex \(x\) is an articulation point if deleting \(x\) and all its incident edges increases the number of connected components. A block is a maximal 2-connected subgraph, or a bridge together with its endpoints, regarded as a \(K_2\) block. Here 2-connected means connected, with at least three vertices, and still connected after deletion of any one vertex. These conventions ensure that bridges are represented as blocks too.
The tree property is the standard result established in the earlier material on the block-cut graph. In this tutorial, a vertex’s tree location means the node just specified. A block node remains in the tree when an articulation-point node is deleted, even if that block contained the deleted vertex. In the original graph, however, the block must then be read after removing that vertex.
The Separation Correspondence
Proof. First suppose that \(u\) and \(w\) are joined by a path in \(G-x\). For each edge of the path, take the block containing that edge. Two consecutive edges either belong to the same block or meet at a vertex that is an articulation point. In the latter case, the two block nodes are connected through that articulation-point node in the block-cut tree. The resulting sequence gives a walk between the tree locations of \(u\) and \(w\). No step uses the node \(x\): the graph path avoids \(x\), and a block containing a non-articulation vertex has that block as its tree location. Thus the locations lie in the same component after deleting the node \(x\).
Conversely, suppose the tree locations of \(u\) and \(w\) lie in the same component of the tree with \(x\) deleted. The unique tree path between those locations avoids \(x\). Each block node \(B\) on this path contributes a connected portion of the original graph after \(x\) is removed. If \(x\notin B\), use all of \(B\), which is connected. If \(x\in B\) and \(B\) is 2-connected, \(B-x\) is connected by the definition of 2-connectedness. If \(B\) is the bridge block \(K_2\) with endpoints \(x\) and \(y\), then \(B-x\) consists of the single vertex \(y\), which is connected. Consecutive block nodes on the tree path meet at an articulation point other than \(x\), so their corresponding portions join at that vertex in \(G-x\). Starting at \(u\), following these connected portions along the tree path reaches \(w\) without using \(x\). Therefore \(u\) and \(w\) lie in the same component of \(G-x\). \(\square\)
Because \(x\) is an articulation point, its tree node has at least two branches when removed. Every such branch contains a block node. The theorem therefore gives a one-to-one correspondence: each component of the tree after deleting \(x\) identifies exactly one component of \(G-x\). The vertices in that graph component are the vertices represented by the branch’s block nodes, with \(x\) excluded. If a block in the branch contains \(x\), use only its remaining vertices.
Reading the Branches in Practice
In the block-cut tree, find the node for the articulation point \(x\).
List the components of the remaining tree. Each begins with a block that was incident to \(x\).
Collect the vertices in its blocks, omit \(x\), and remember that a block containing \(x\) contributes only its other vertices.
Two surviving vertices are connected after deletion exactly when their tree locations are in the same remaining tree component.
Worked Example: Deleting Either of Two Articulation Points
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7,8,9\}\) and \(E=\{12,23,13,34,45,56,36,67,68,89,96\}\). The blocks are \(A=\{1,2,3\}\), \(B=\{3,4,5,6\}\), \(C=\{6,7\}\), and \(D=\{6,8,9\}\). Here \(A\) and \(D\) are triangles, \(B\) is a 4-cycle, and \(C\) is a bridge block. The articulation points are \(3\) and \(6\).
The block-cut tree has block nodes \(A,B,C,D\) and articulation-point nodes \(3,6\), with edges \(A3,B3,B6,C6,D6\). It has six nodes and five edges, and the listed adjacencies form a connected tree. The edge list also gives \(3+4+1+3=11\) graph edges, matching the 11 edges displayed in \(E\).
Delete node \(3\) from the tree. One branch consists of \(A\) alone; the other consists of \(B\), followed by \(6\), with \(C\) and \(D\) branching from \(6\). Translating the first branch gives \(A-3=\{1,2\}\). Translating the other gives \(\{4,5,6,7,8,9\}\). Thus \(G-3\) has components \(\{1,2\}\) and \(\{4,5,6,7,8,9\}\).
Now delete node \(6\) instead. The remaining tree has three branches: the branch through \(B\) and \(3\) to \(A\), the single block \(C\), and the single block \(D\). They translate to \(\{1,2,3,4,5\}\), \(\{7\}\), and \(\{8,9\}\). Hence \(G-6\) has three components. The bridge block \(C=\{6,7\}\) contributes only the singleton \(\{7\}\) after deletion.
Check: The components found for \(G-6\) account for all eight surviving vertices: \(5+1+2=8=|V|-1\). The displayed edges of \(G-6\) are \(12,23,13,34,45,68,89,96\): the first five connect \(\{1,2,3,4,5\}\), the next two connect \(\{8,9\}\), and vertex \(7\) has no incident edge.
Worked Example: Testing Whether Two Vertices Stay Connected
Let \(G=(V,E)\), with \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{ab,bc,ca,cd,de,ef,fd,dg\}\). Its blocks are the triangle \(\{a,b,c\}\), the bridge block \(\{c,d\}\), the triangle \(\{d,e,f\}\), and the bridge block \(\{d,g\}\). The articulation points are \(c\) and \(d\). The block-cut tree is the path from the first triangle through \(c\), the bridge \(\{c,d\}\), and \(d\) to the second triangle, with the bridge \(\{d,g\}\) also attached at \(d\).
Delete \(d\). The tree has three branches: the one through \(c\) and the first triangle, the second triangle, and the bridge \(\{d,g\}\). They correspond to \(\{a,b,c\}\), \(\{e,f\}\), and \(\{g\}\), respectively. The block \(\{c,d\}\) is in the first branch and contributes \(c\) after \(d\) is removed; the bridge \(\{d,g\}\) contributes \(g\).
For example, the tree locations of \(a\) and \(c\) are in the same branch, so the theorem says they remain connected. Indeed, the edges \(ab,bc,ca\) still connect them. The locations of \(a\) and \(e\) are in different branches, so they are disconnected in \(G-d\). This also follows directly: after deleting \(d\), the only edges are \(ab,bc,ca,ef,fd\) with \(fd\) removed, leaving the triangle on \(\{a,b,c\}\) and the edge \(ef\), as well as the isolated vertex \(g\).
Check: The original edge list has \(3+1+3+1=8\) edges. Deleting \(d\) removes \(cd,de,fd,dg\), leaving \(8-4=4\) edges: \(ab,bc,ca,ef\). These edges give exactly the three components stated.
Worked Example: A Chain of Three Blocks
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,23,13,34,45,35,56,67,57\}\). The blocks are the triangles on \(\{1,2,3\}\), \(\{3,4,5\}\), and \(\{5,6,7\}\), joined in a chain. The articulation points are \(3\) and \(5\), so the block-cut tree is a path through the first triangle, \(3\), the middle triangle, \(5\), and the last triangle.
Delete \(3\). Removing its tree node leaves one branch containing the first triangle and one branch containing the middle and last triangles through \(5\). In the graph, these branches give \(\{1,2\}\) and \(\{4,5,6,7\}\). In particular, the locations of \(1\) and \(7\) lie on opposite sides of node \(3\), so no path between them survives in \(G-3\).
Deleting \(5\) instead leaves the first and middle triangles together on one side, and the last triangle on the other. The resulting components are \(\{1,2,3,4\}\) and \(\{6,7\}\). The two answers can also be checked directly from the edges: deleting \(3\) leaves \(12,45,35,56,67,57\), while deleting \(5\) leaves \(12,23,13,34,67\). In each list, the edges connect exactly the vertex sets identified by the corresponding tree branches.
Common Pitfall: A Block Node Is Not an Unchanged Block
Deleting an articulation-point node from the block-cut tree is a way to identify branches; it does not mean that every block in a branch remains intact in the graph. In particular, a block incident to the deleted vertex loses that vertex and all its incident edges. A 2-connected block remains connected after that deletion, but a bridge block leaves only its other endpoint.
For instance, in the first example, it would be wrong to report \(\{6,7\}\) as a component of \(G-6\). The bridge block node \(C\) is a branch of the tree with node \(6\) deleted, but the graph vertex \(6\) itself has also been deleted. The correct component is \(\{7\}\). Likewise, the triangle \(\{6,8,9\}\) contributes the connected pair \(\{8,9\}\), not the unchanged triangle.
The same distinction prevents another error: a branch is not just one block. In the first example, after node \(3\) is removed, the branch beginning at \(B\) also contains node \(6\) and the blocks \(C,D\). All of those blocks belong to the same component of \(G-3\), because their tree nodes remain connected without passing through \(3\).
Why the Tree View Is Useful
The separation correspondence replaces repeated path searches in the original graph with a simpler question about a tree. Once the block-cut tree is known, the components after deleting an articulation point are the branches at its node. To decide whether two vertices remain connected, locate them in the tree and test whether the unique path between their locations passes through the deleted node. If it does, they become disconnected; if it does not, they remain connected.
This viewpoint also explains how blocks remain connected through each surviving component. A component may contain several blocks joined at articulation points other than the one deleted. A block containing the deleted point contributes its connected remainder, or a single vertex when it was a bridge. The tree records exactly which such pieces still join together.
Check Your Understanding
For each question, use the block-cut tree and state how the relevant branch translates to vertices of the graph.
- In the first worked example, which component of \(G-3\) contains vertex \(8\), and what tree branch identifies it?
- In the second worked example, do \(a\) and \(g\) remain connected after deleting \(c\)? Justify your answer using their tree locations.
- In the third worked example, list the components after deleting \(5\), and verify that every vertex other than \(5\) appears exactly once.
- Explain why a bridge block \(\{x,y\}\) incident to the deleted articulation point \(x\) contributes \(\{y\}\), not \(\{x,y\}\).
- State the theorem’s test for whether two vertices \(u,w\ne x\) remain connected after deleting an articulation point \(x\).