From Edge Lists to Block Structure
Cut vertices, bridges and blocks describe how a connected graph is assembled from pieces that cannot be separated by deleting one vertex. The block-cut tree records those pieces and their points of attachment. Open ear decompositions provide a complementary description of 2-connected graphs: start with a cycle and add paths whose endpoints are already present while their internal vertices are new. The worked problems below use edge lists throughout, so each conclusion can be checked without relying on a drawing.
Maximality in the block definition means maximal under inclusion as a subgraph, not merely a piece that happens to be 2-connected. A bridge is included as its own block even though its two-vertex graph is not 2-connected under the definition above. A connected graph consisting of a single vertex, \(K_1\), has no cut vertices, bridges or blocks under these conventions; its block-cut incidence graph is empty, not a tree. The standard block-cut tree result therefore applies to connected graphs with at least two vertices: their block-cut incidence graph is a tree. This result was established in the earlier material on block-cut trees.
For deletion checks, it helps to be precise about what is being counted. Deleting a vertex removes it and all its incident edges; deleting an edge leaves its endpoints in the graph. A vertex is a cut vertex only if the number of components increases, and an edge is a bridge only if the number of components increases. In a connected graph, a bridge is also characterized as an edge on no cycle, as shown in the earlier material on bridges.
Worked Problems: Blocks and the Block-Cut Tree
Worked Example: A Chain of Blocks
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7,8\}\) and \(E=\{12,23,31,34,45,56,67,74,78\}\). Find its cut vertices, bridges, blocks and block-cut incidence tree.
The edges \(12,23,31\) form a triangle on \(\{1,2,3\}\). The edge \(34\) joins that triangle to the cycle \(4,5,6,7,4\), whose edges are \(45,56,67,74\). Finally, \(78\) attaches vertex \(8\) at vertex \(7\).
Deleting vertex \(3\) separates \(\{1,2\}\) from \(\{4,5,6,7,8\}\), so \(3\) is a cut vertex. Deleting \(4\) separates \(\{1,2,3\}\) from \(\{5,6,7,8\}\), so \(4\) is a cut vertex. Deleting \(7\) isolates \(8\) from \(\{1,2,3,4,5,6\}\), so \(7\) is a cut vertex. Deleting any other vertex leaves the graph connected: in the triangle, the other two vertices remain joined by an edge; in the 4-cycle, the other three vertices remain joined by a path; and deleting \(8\) only removes its leaf edge. Thus the cut vertices are exactly \(\{3,4,7\}\).
The edge \(34\) is a bridge because deleting it separates the triangle from the rest of the graph. The edge \(78\) is a bridge because deleting it isolates \(8\). Each of the other seven edges lies on one of the displayed cycles: \(12,23,31\) lie on the triangle, and \(45,56,67,74\) lie on the 4-cycle. Hence those edges are not bridges.
The four blocks are the triangle on \(\{1,2,3\}\), the bridge block on \(\{3,4\}\), the 4-cycle on \(\{4,5,6,7\}\), and the bridge block on \(\{7,8\}\). The triangle and 4-cycle are maximal 2-connected subgraphs: each is 2-connected, and adding vertices from beyond its attachment points would include a cut vertex as a separating point. The two remaining edges are bridge blocks.
Write \(B_1,B_2,B_3,B_4\) for those blocks in the order just given, and \(c_3,c_4,c_7\) for the cut-vertex nodes. The incidence edges are \(B_1c_3\), \(B_2c_3\), \(B_2c_4\), \(B_3c_4\), \(B_3c_7\), and \(B_4c_7\). There are \(4+3=7\) nodes and \(6\) incidence edges, and the listed incidences form the path \(B_1-c_3-B_2-c_4-B_3-c_7-B_4\), a tree.
Check: the original graph has \(8\) vertices and \(9\) edges: three triangle edges, one bridge \(34\), four cycle edges and one bridge \(78\), for \(3+1+4+1=9\). The block-cut tree has \(7\) nodes and \(6=7-1\) edges, in agreement with its explicit path structure.
The block-cut tree is useful because it records attachments without retaining every edge inside each block. It also gives a quick way to check whether a proposed list is complete: every bridge must appear as a bridge block, and each cut vertex must be incident in the incidence graph with every block containing it. The next example illustrates why edges shared by cycles should not automatically be treated as bridges or as boundaries between blocks.
Worked Example: Two Cycles Sharing an Edge
Let \(H=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,31,34,45,52\}\). Determine its cut vertices, bridges and blocks, and give an open ear decomposition.
The edges \(23,34,45,52\) form the cycle \(2,3,4,5,2\). The remaining two edges \(21,13\) form the path \(2,1,3\), whose endpoints \(2,3\) are distinct vertices of that cycle and whose internal vertex \(1\) is new. Thus an ear decomposition is \(P_0=2,3,4,5,2\), followed by \(P_1=2,1,3\).
To verify 2-connectivity directly, delete each vertex in turn. Deleting \(1\) leaves the cycle \(2,3,4,5,2\). Deleting \(2\) leaves the connected path \(1,3,4,5\). Deleting \(3\) leaves the connected path \(1,2,5,4\). Deleting \(4\) leaves the triangle \(1,2,3,1\) together with edge \(25\), which is connected. Deleting \(5\) leaves the triangle \(1,2,3,1\) together with edge \(34\), also connected. The graph is connected and has five vertices, so it is 2-connected and is its own block.
No edge is a bridge: \(12,23,31\) lie on the triangle \(1,2,3,1\), while \(23,34,45,52\) lie on the 4-cycle. Since \(H\) is 2-connected, it has no cut vertices. Its block-cut incidence graph therefore consists of a single block node and no cut-vertex nodes.
Check: the initial cycle uses four edges, \(23,34,45,52\), and the added ear uses the other two, \(21,13\). The total is \(4+2=6=|E|\); every edge appears exactly once in the decomposition.
Open Ears and 2-Connectivity
The condition that the endpoints be distinct matters: a path returning to the same old vertex is a closed addition, not an open ear. An ear with internal vertices must introduce all of those vertices as new at that stage. These conditions ensure that the added path attaches to the existing graph at its two ends, rather than at several intermediate vertices.
Proof. Write \(P=x,v_1,\ldots,v_k,y\), where \(x\ne y\) belong to \(H\) and the \(v_i\) are new. The union is connected because \(H\) is connected and every vertex of \(P\) is joined along the path to \(x\) or \(y\). It has at least three vertices since \(H\) does. To prove it remains connected after deletion of any vertex \(z\), first suppose \(z\in V(H)\). The graph \(H-z\) is connected. If \(z=x\), the remaining part of the ear is attached to \(y\); if \(z=y\), it is attached to \(x\). If \(z\) is neither endpoint, the ear remains intact and attaches to \(H-z\) at both endpoints. In each case the remaining union is connected. Now suppose \(z=v_i\) is internal to the ear. The graph \(H\) remains intact and connected. The part of the ear from \(x\) to the vertex just before \(z\), if nonempty beyond \(x\), is attached to \(H\) at \(x\); the part from just after \(z\) to \(y\), if nonempty before \(y\), is attached at \(y\). Thus every remaining vertex of the ear lies in the same component as \(H\). This proves that deleting any vertex leaves the union connected, so \(H\cup P\) is 2-connected. \(\square\)
By applying the theorem after each addition, every partial graph in an open ear decomposition that starts with a cycle remains 2-connected. A cycle is 2-connected because deleting any one of its vertices leaves a path on the remaining vertices. The theorem just proved therefore supplies a direct check on the connectivity of each stage; the final edge and vertex lists must still be checked to ensure the decomposition describes the intended graph.
Worked Example: Building a Graph in Three Ears
Let \(J=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,41,15,53,26,64,56\}\). Construct an open ear decomposition and verify the resulting graph.
Start with the cycle \(P_0=1,2,3,4,1\), using edges \(12,23,34,41\). Add \(P_1=1,5,3\). Its endpoints \(1,3\) are in \(P_0\), and its internal vertex \(5\) is new; it adds edges \(15,53\). Next add \(P_2=2,6,4\). Its endpoints \(2,4\) are already present, and its internal vertex \(6\) is new; it adds \(26,64\). Finally add \(P_3=5,6\), a single-edge open ear. Its distinct endpoints are already present, and the edge \(56\) has not previously been added.
Each step satisfies the open-ear conditions. The first ear introduces vertex \(5\), the second introduces vertex \(6\), and the final ear introduces no vertex but adds a new edge. The union therefore contains all six vertices. Its edge set is the four edges of \(P_0\), the two of \(P_1\), the two of \(P_2\), and the one of \(P_3\), a total of \(4+2+2+1=9\) distinct edges. This is exactly the specified set \(E\).
The ear-extension theorem proves that each partial graph is 2-connected, and hence \(J\) is 2-connected. As a direct check, after deleting vertex \(1\), the remaining vertices are connected by \(2-3-4\) together with \(3-5-6-2\). After deleting \(2\), the remaining vertices are connected by \(3-4-1-5-3\), with \(5-6-4\) attached. After deleting \(3\), the remaining vertices are connected by \(2-1-4-6-2\), with \(1-5-6\) attached. After deleting \(4\), the remaining vertices are connected by \(1-2-3-5-1\), with \(2-6-5\) attached. After deleting \(5\), the cycle \(1-2-3-4-1\) remains and vertex \(6\) is joined to \(2\) and \(4\). After deleting \(6\), that same cycle remains and vertex \(5\) is joined to \(1\) and \(3\). Every deletion leaves a connected graph.
Check: the four ears account for \(9\) edges, matching \(|E|=9\). The direct deletion checks also confirm 2-connectivity independently of the ear-extension argument. Thus \(J\) is one block, has no cut vertices, and has no bridges.
Common Pitfalls and a Reliable Check
Forgetting bridge blocks gives the wrong incidence graph. In the first worked example, suppose the bridge edges \(34\) and \(78\) are omitted from the block list. The proposed nodes would be the triangle, the 4-cycle, and cut vertices \(3,4,7\). The only incidences would be triangle–\(3\), 4-cycle–\(4\), and 4-cycle–\(7\). This gives five nodes and three edges, but it leaves the triangle side disconnected from the 4-cycle side in the proposed incidence graph. The correction is to include both bridge blocks: the resulting seven-node graph has six incidence edges and is the path displayed above.
Do not apply the block-cut tree statement to \(K_1\) under these conventions. The connected graph \(K_1\) has no cut vertices, bridges or blocks, so its incidence graph has zero nodes. A tree is connected and has at least one node; the empty graph is not a tree. State the result for connected graphs with at least two vertices, or explicitly adopt a different convention that treats the lone vertex as a degenerate block.
For a worked problem, a dependable order is to test vertex deletions for cut vertices, test edges for bridges, identify maximal 2-connected subgraphs, include a block for each bridge, and then list the block-cut incidences. For an ear decomposition, list the initial cycle and every subsequent path, checking at each stage that the endpoints are distinct old vertices, the internal vertices are new, and no listed edge has already appeared. Finish by comparing the union of the listed vertices and edges with the graph specified in the problem.
Check Your Understanding
Use explicit deletion checks and edge lists to support your answers.
- For the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\), find the cut vertices, bridges, blocks and block-cut incidence tree.
- Explain why the graph \(K_1\) does not have a block-cut incidence tree under the conventions in this tutorial.
- Give an open ear decomposition of the graph with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,41,13,35,52\}\), or explain which condition prevents the proposed sequence from being one.
- For an open ear with no internal vertices, state precisely what the ear adds and why its endpoints must be distinct.
- In the third worked example, which ear adds no new vertex, and which condition does it satisfy that makes it an open ear?