From an Edge List to Blocks
A list of edges specifies a graph, but its blocks are not always apparent from the list alone. The task is to identify which edges lie together in a maximal 2-connected subgraph, which edges are bridges on their own, and which vertices belong to more than one block. In particular, a shared vertex does not by itself combine two pieces into one block.
All graphs in this tutorial are finite and simple. A graph is connected if every two of its vertices are joined by a path. A vertex \(v\) is a cut vertex of a connected graph if deleting \(v\) and its incident edges leaves a disconnected graph. A connected graph with at least three vertices is 2-connected if deleting any one vertex leaves a connected graph. Here, a graph with one vertex is connected; this convention applies when testing what remains after deletion.
A bridge is an edge whose deletion increases the number of connected components. The earlier material on bridges gives the equivalent test that an edge is a bridge exactly when it lies on no cycle. We will use this test, and also verify bridge claims directly when working an example. For a connected graph with at least three vertices, 2-connectivity can be tested by deleting each vertex in turn: every resulting graph must remain connected.
A Systematic Edge-List Procedure
For a small graph, one reliable method is to test vertex sets. For each set \(S\) of at least three vertices, form the induced subgraph \(G[S]\): its vertices are \(S\), and it includes every edge of \(G\) whose two endpoints are in \(S\). Keep \(S\) as a candidate precisely when \(G[S]\) is connected and \(G[S]-v\) is connected for every \(v\in S\). Among these candidates, retain the sets maximal under inclusion. Their induced subgraphs are the maximal 2-connected pieces.
Then account for every edge not in one of those pieces. Such an edge is a bridge and forms its own block. An isolated vertex, if present, forms a one-vertex block. Finally, list the vertices that occur in more than one block. This last record is important: the edges of two blocks are disjoint, but their vertex sets can overlap.
Write down the vertex set and every listed edge. Separate connected components if the graph is disconnected.
For each candidate set \(S\) with at least three vertices, check that \(G[S]\) is connected and remains connected after deletion of each vertex of \(S\).
If one passing set is contained in a larger passing set, it is not a separate block.
Make each unused edge a bridge block, list isolated vertices, and record any vertices shared by blocks.
Testing every vertex set can require substantial work for a large graph, but the procedure gives a direct and unambiguous method for explicit small examples. Its correctness follows from the decomposition fact below.
Why the Procedure Finds the Blocks
Proof. Let \(e=uv\) be an edge that is not a bridge. By the bridge-cycle criterion, \(e\) lies on a cycle \(C\). A cycle is 2-connected: deleting any one of its vertices leaves a path through all the remaining vertices, which is connected. Thus \(C\) is a 2-connected subgraph containing \(e\). Since the graph is finite, we can enlarge \(C\), whenever possible, to a 2-connected subgraph maximal under inclusion. Hence \(e\) belongs to a maximal 2-connected subgraph.
Next, suppose two 2-connected subgraphs \(H_1,H_2\) share at least two vertices. Their union is connected. If any vertex \(x\) is deleted from the union, each \(H_i-x\) remains connected when \(x\in V(H_i)\); if \(x\notin V(H_i)\), that subgraph is unchanged and remains connected. At least one of the two shared vertices remains after deleting \(x\), so the two remaining subgraphs still meet. Their union after deletion is therefore connected. The union has at least three vertices and is 2-connected. Consequently, two distinct maximal 2-connected subgraphs cannot share two or more vertices: their union would be a strictly larger 2-connected subgraph.
We have shown that every nonbridge edge belongs to a maximal 2-connected subgraph. Conversely, an edge in a 2-connected subgraph lies on a cycle of that subgraph: if it lay on no cycle, it would be a bridge there; deleting one of its endpoints would disconnect the subgraph, contrary to 2-connectivity. It therefore cannot be a bridge of the original graph, since a cycle in a subgraph is also a cycle in the original graph. Thus the edges not in maximal 2-connected subgraphs are precisely bridges. Distinct such subgraphs cannot share an edge, by the result about their intersections, and a bridge cannot be in one of them. Isolated vertices have no incident edges and are accounted for separately. This proves the decomposition claim. \(\square\)
The vertex-set test indeed finds these maximal subgraphs. If a maximal 2-connected subgraph omitted an edge of \(G\) joining two of its vertices, adding that edge would preserve connectivity after every vertex deletion. The subgraph would still be 2-connected, contradicting maximality. It must therefore be induced on its vertex set. Conversely, an induced subgraph passing all the deletion tests is 2-connected by definition, and a passing set maximal under inclusion gives a maximal 2-connected subgraph.
Worked Edge-List Examples
Worked Example: Two Triangles Joined by a Bridge
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,34,45,56,64\}\). The edges \(12,23,31\) form one triangle, the edges \(45,56,64\) form another, and \(34\) joins them. Find the blocks and the shared vertices.
First test \(S_1=\{1,2,3\}\). The induced edges are \(12,23,31\), so \(G[S_1]\) is connected. Deleting 1 leaves the edge \(23\), which is connected; deleting 2 leaves \(31\), which is connected; deleting 3 leaves \(12\), which is connected. Thus \(G[S_1]\) is 2-connected. For \(S_2=\{4,5,6\}\), the induced edges are \(45,56,64\). Deleting 4 leaves \(56\), deleting 5 leaves \(64\), and deleting 6 leaves \(45\); each is connected. Thus \(G[S_2]\) is also 2-connected.
To check maximality, divide the vertices into the two sets \(\{1,2,3\}\) and \(\{4,5,6\}\). Edge \(34\) is the only edge between these sets. Any connected subgraph containing vertices from both sets must include \(34\) and both its endpoints. Removing \(34\) from that subgraph separates its selected vertices on one side from its selected vertices on the other. So \(34\) is a bridge in that subgraph, which rules out 2-connectivity. In particular, no 2-connected subgraph can enlarge either triangle to include vertices from the other side. The edge \(34\) itself is a bridge block.
Check: The block edge sets are \(\{12,23,31\}\), \(\{45,56,64\}\), and \(\{34\}\). Their sizes add to \(3+3+1=7=|E|\), and they are pairwise disjoint. Their vertex sets are \(\{1,2,3\}\), \(\{4,5,6\}\), and \(\{3,4\}\); vertices 3 and 4 each belong to two blocks.
Worked Example: Two Blocks Meeting at a Cut Vertex
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,34,45,53,36\}\). There are triangles \(1,2,3,1\) and \(3,4,5,3\), with an extra edge \(36\). Find all the blocks.
For \(S_1=\{1,2,3\}\), the induced edges are \(12,23,31\). Deleting 1 leaves \(23\), deleting 2 leaves \(31\), and deleting 3 leaves \(12\); each remaining graph is connected. Thus \(S_1\) gives a 2-connected subgraph. For \(S_2=\{3,4,5\}\), the induced edges are \(34,45,53\). Deleting 3 leaves \(45\), deleting 4 leaves \(53\), and deleting 5 leaves \(34\), again connected in each case. Thus \(S_2\) also gives a 2-connected subgraph.
These triangles share only vertex 3. If a connected subgraph includes vertices from both triangles, it must use vertex 3 to connect them. Deleting 3 separates any selected vertices from \(\{1,2\}\) from selected vertices in \(\{4,5\}\). Such a subgraph cannot be 2-connected, so neither triangle can be enlarged to a 2-connected subgraph containing vertices from the other triangle. Edge \(36\) is a bridge because it is the only edge incident to vertex 6. The blocks are therefore the two triangle blocks and the single-edge block \(36\).
Check: The three block edge sets contain \(3+3+1=7\) distinct edges, equal to \(|E|=7\). Their vertex sets are \(\{1,2,3\}\), \(\{3,4,5\}\), and \(\{3,6\}\). Vertex 3 belongs to all three blocks; no other vertex is shared.
Worked Example: Two Triangles Sharing an Edge
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,31,24,34,45\}\). The vertices \(1,2,3,4\) form two triangles sharing edge \(23\). Find the blocks.
Test \(S=\{1,2,3,4\}\). Its induced edges are \(12,23,31,24,34\). After deleting 1, the remaining edges \(23,24,34\) connect \(2,3,4\). After deleting 2, the remaining edges \(31,34\) connect \(1,3,4\). After deleting 3, the remaining edges \(12,24\) connect \(1,2,4\). After deleting 4, the remaining edges \(12,23,31\) connect \(1,2,3\). Thus the induced subgraph on \(S\) is 2-connected.
Adding vertex 5 to this candidate adds only edge \(45\). This edge is the only connection from 5 to the other vertices, so it is a bridge in the enlarged graph; the enlarged graph cannot be 2-connected. Hence the maximal 2-connected block has vertex set \(\{1,2,3,4\}\), and edge \(45\) is a bridge block.
Check: The core block has five edges, and the bridge block has one, giving \(5+1=6=|E|\). The two original triangles do not form separate blocks: their union on \(\{1,2,3,4\}\) passes all four deletion tests. Vertex 4 belongs to both the core block and the bridge block.
Common Mistakes and Practical Checks
Mistake: stopping at the first cycles found. In the last example, finding the triangles \(1,2,3,1\) and \(2,3,4,2\) does not mean that they are separate blocks. Their union remains connected after deletion of each of its four vertices, as the calculations show. The maximal 2-connected piece includes both triangles and their shared edge.
Mistake: treating a shared vertex as a shared edge. In the second example, both triangle blocks contain vertex 3, but no edge belongs to both. They cannot be merged just because they meet at 3: deleting 3 separates their other vertices. When checking a proposed larger block, test the deletion condition rather than relying on how many pieces appear to meet.
Mistake: using only the edge list of a candidate cycle. The candidate for a block on vertex set \(S\) must use all edges of \(G[S]\), not just the edges of a cycle chosen inside \(S\). Extra edges can affect connectivity, and maximality is tested by considering larger vertex sets. In these examples, every block edge set is explicitly accounted for; an edge omitted from the 2-connected pieces must be checked as a bridge, not silently discarded.
For a final audit, verify that each listed edge appears in exactly one block, that each proposed 2-connected block stays connected after every single-vertex deletion, and that no such block can be enlarged. Record shared vertices separately. This produces the block list directly from the edge list without conflating the blocks with the later incidence structure built from them.
Check Your Understanding
For each question, use the edge list to justify the block assignment and check that every edge is accounted for.
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\). Find the blocks and the vertices belonging to more than one block.
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41,13\}\). Test whether the induced subgraph on all four vertices is 2-connected by deleting each vertex.
- Explain why two distinct maximal 2-connected subgraphs cannot share two vertices.
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,31\}\). Identify the block containing vertex 4 and explain why it is not a bridge block.
- Give a concrete wrong block assignment for the graph in Worked Example: Two Triangles Sharing an Edge, and correct it using the deletion tests.