What a Block Captures
A connected graph can contain regions that remain connected after any one vertex is removed, joined to one another at cut vertices or by bridges. A block is a maximal connected subgraph with no cut vertex. The word “maximal” is important: a block cannot be enlarged within the given graph while retaining the defining property. It need not have the largest number of vertices among all such subgraphs.
All graphs in this tutorial are finite and simple. For a graph \(H\), let \(c(H)\) denote its number of connected components, with \(c(\varnothing)=0\). For a vertex \(x\in V(H)\), the notation \(H-x\) means delete \(x\) and all edges incident with it.
The component-count definition handles small cases without exceptions: deleting the only vertex of \(K_1\) gives \(0<1\) components, and deleting either vertex of \(K_2\) leaves one component, just as before. Thus neither \(K_1\) nor \(K_2\) has a cut vertex. In a connected graph with at least two vertices, having no cut vertex means that deleting any one vertex leaves a connected graph.
This definition gives the standard conventions automatically. A bridge edge, viewed by itself as a \(K_2\), can be a block; an isolated vertex, viewed as a \(K_1\), is a block. In contrast, a single vertex in a nontrivial connected component is not a block, since it can be enlarged to include an incident edge.
How Blocks Can Overlap
The following fact explains why a block is a coherent piece: two connected subgraphs with no cut vertex cannot overlap in two vertices without together forming a larger connected subgraph with no cut vertex.
Proof. Since \(A\) and \(B\) share vertices, their union is connected. Fix any vertex \(x\in V(A\cup B)\). Each of \(A-x\) and \(B-x\), when nonempty, is connected: if \(x\) belongs to that subgraph this follows from the absence of cut vertices, and if it does not, the subgraph is unchanged. At least one vertex of \(A\cap B\) remains after deleting \(x\), because the intersection contains at least two vertices. Thus the remaining parts of \(A\) and \(B\) still meet, and \((A\cup B)-x\) is connected whenever it is nonempty. If the union has order one, it has no cut vertex by the component-count definition. In all cases deletion of \(x\) does not increase the number of components. Therefore \(A\cup B\) has no cut vertex. \(\square\)
Proof. Suppose distinct blocks \(B_1\) and \(B_2\) shared at least two vertices. By the Lemma, \(B_1\cup B_2\) would be a connected subgraph with no cut vertex. It contains each \(B_i\), so maximality of each block forces \(B_1=B_1\cup B_2=B_2\), a contradiction. Hence distinct blocks share at most one vertex.
For any edge \(uv\), the subgraph on \(\{u,v\}\) with edge \(uv\) is connected and has no cut vertex. Because the graph is finite, it can be enlarged, if necessary, until it is maximal among connected subgraphs with no cut vertex. This gives a block containing \(uv\). If two blocks contained \(uv\), they would share both \(u\) and \(v\), contradicting the first part; therefore the block is unique. Finally, every nonisolated vertex is incident with an edge and hence belongs to its block. Each isolated vertex forms its own \(K_1\) block. \(\square\)
Worked Examples
Worked Example: Two Triangles, a Bridge, and an Isolated Edge
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7,8\}\) and \(E=\{12,23,31,34,45,53,56,78\}\). Determine its blocks and the block memberships of its vertices and edges.
The edges \(12,23,31\) form the triangle on \(\{1,2,3\}\). Removing any one of its vertices leaves the other two joined by an edge, so this triangle has no cut vertex. Likewise, \(34,45,53\) form a triangle on \(\{3,4,5\}\), and deleting any one of its vertices leaves the remaining edge. These are candidate blocks.
The first triangle can be enlarged to a connected subgraph only by adding vertices through vertex \(3\). If any such outside vertices are included, deleting \(3\) separates the added vertices from the remaining vertices \(1\) and \(2\). Thus the first triangle is maximal with no cut vertex. For the second triangle, outside vertices can be reached through \(3\) or \(5\). If vertices are added only through \(3\), deleting \(3\) separates them from \(4,5\); if they are added only through \(5\), deleting \(5\) separates them from \(3,4\). If additions occur through both sides, deleting either attachment vertex separates the vertices on that side. So the second triangle is also maximal with no cut vertex.
The edge \(56\) is a bridge: it is the only connection from vertex \(6\) to the rest of its component. The subgraph consisting of \(56\) is a \(K_2\), which has no cut vertex. Any connected enlargement containing vertices beyond \(5,6\) must add vertices through \(5\); deleting \(5\) then separates \(6\) from those added vertices. Hence \(56\) is a block. The separate component with edge \(78\) is \(K_2\), so it is another block.
The blocks are therefore the triangles on \(\{1,2,3\}\) and \(\{3,4,5\}\), and the \(K_2\) subgraphs on \(\{5,6\}\) and \(\{7,8\}\). Vertex \(3\) belongs to both triangle blocks, and vertex \(5\) belongs to the second triangle and the \(56\) block. Each other vertex belongs to just one of these blocks. The edge lists partition as \(\{12,23,31\}\), \(\{34,45,53\}\), \(\{56\}\), and \(\{78\}\).
Check: the four edge sets contain \(3+3+1+1=8\) edges, which is \(|E|=8\). No edge has been assigned to two blocks, and the only vertices shared by distinct blocks are \(3\) and \(5\), one vertex at a time.
Worked Example: A 2-Connected Core with a Two-Edge Tail
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,41,13,45,56\}\). The first four vertices form a square with a diagonal. Determine the blocks.
Let \(H\) be the subgraph with vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34,41,13\}\). Deleting \(1\) leaves the connected path \(2,3,4\); deleting \(2\) leaves \(1,3,4\) connected by \(13,34,41\); deleting \(3\) leaves \(1,2,4\) connected by \(12,14\); and deleting \(4\) leaves \(1,2,3\) connected by \(12,23,13\). Thus \(H\) has no cut vertex.
Any connected subgraph that enlarges \(H\) must include vertex \(5\), and if it includes \(6\), it must also include \(5\). The only connection from the added vertices to \(H\) is through \(4\). Deleting \(4\) separates the added vertices from the vertices of \(H-\{4\}\), so no such enlargement has no cut vertex. Therefore \(H\) is a block.
The edge \(45\) is a block by itself: including vertices from \(H\) attaches them through \(4\), while including \(6\) attaches it through \(5\). If both sides are included, deleting \(4\) or \(5\) separates one side from the other. Similarly, \(56\) is a block: adding vertices beyond its endpoints requires adding the core through \(5\), and deleting \(5\) separates vertex \(6\) from the rest. The complete block list is therefore \(H\), \(K_2\) on \(\{4,5\}\), and \(K_2\) on \(\{5,6\}\).
Check: the core has \(5\) edges and the two \(K_2\) blocks have \(1\) edge each, giving \(5+1+1=7=|E|\). The blocks share only vertex \(4\) between the core and \(45\), and vertex \(5\) between \(45\) and \(56\).
Worked Example: Blocks in a Path and an Isolated Component
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,cd\}\). The vertex \(e\) is isolated. Find every block.
Each edge, considered on its own, is a \(K_2\) with no cut vertex. A connected subgraph containing two consecutive edges of the path, such as \(ab\) and \(bc\), has \(b\) as a cut vertex: deleting \(b\) separates \(a\) from \(c\). The same argument applies to \(bc,cd\), with cut vertex \(c\). The whole path has cut vertices \(b\) and \(c\), so it is not a block. Therefore the three edge-subgraphs \(ab\), \(bc\), and \(cd\) are maximal connected subgraphs with no cut vertex.
The isolated vertex \(e\) is itself a connected subgraph with no cut vertex. It cannot be enlarged to a connected subgraph because it has no incident edge, so \(\{e\}\) is a block. The four blocks are the three \(K_2\) edge-subgraphs and the singleton \(\{e\}\).
Check: the three edge blocks account for exactly \(3=|E|\) edges. The path vertices \(b\) and \(c\) each belong to two blocks; \(a,d\), and the isolated vertex \(e\) each belong to one.
Common Mistake: Connected Does Not Mean a Block
A connected graph is not necessarily a block. For example, the path on vertices \(\{a,b,c\}\) with edges \(\{ab,bc\}\) is connected, but deleting \(b\) leaves two components, so \(b\) is a cut vertex. A mistaken conclusion would be: “The graph is connected, so the whole path is one block.” The correction is to test the no-cut-vertex condition as well as connectedness. Its two blocks are the \(K_2\) subgraphs \(ab\) and \(bc\).
Another common error is to exclude bridges and isolated vertices because they are too small to be 2-connected. The block definition used here is maximal connected with no cut vertex, not “2-connected with at least three vertices.” Under this convention, a bridge is a \(K_2\) block when it cannot be enlarged without creating a cut vertex, and an isolated vertex is a \(K_1\) block. In a nontrivial component, however, a single vertex alone is not maximal if it has an incident edge.
The overlap and edge-membership facts are useful when reading a block decomposition: each edge is accounted for once, while a vertex can be shared by several blocks. In particular, finding that two distinct blocks share two vertices signals an error, since their union would still have no cut vertex and would contradict maximality.
Check Your Understanding
Use the definition of a block, including its maximality condition, in each question.
- Let \(G\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,31,34\}\). List its blocks and identify any vertex that belongs to more than one.
- Explain why \(K_2\) has no cut vertex using the component-count definition.
- Can two distinct blocks share an edge? Justify your answer using the overlap result.
- Let \(G\) be a path on five vertices. How many blocks does it have, and which vertices belong to more than one block?
- Why does every isolated vertex form a block, while a nonisolated vertex considered by itself does not?