From finding a cut vertex to understanding the graph
Two triangles sharing one vertex have no bridges, but deleting their common vertex separates them. A bridge forest therefore cannot describe all single-vertex failures. A list of cut vertices does not describe them fully either: it tells us which vertices are vulnerable, but not which parts of the graph they connect.
The right pieces may overlap. Each triangle in this example should remain a piece, so their shared cut vertex must belong to both. We will define these pieces precisely and prove that their pattern of attachment is a forest. The forest then answers a concrete question: which individual vertices, other than the endpoints, separate two specified vertices?
Throughout, is a finite simple undirected graph, possibly disconnected or empty. Write for its number of connected components. Deleting a vertex deletes its incident edges too.
Definition 9.1.1
(Cut vertex)
A cut vertex of a graph is a vertex with .
The empty graph has zero components; the one-vertex graph has no cut vertex.
Pieces that may share a vertex
Definition 9.1.2
(Block)
A block of is a connected subgraph with no cut vertex that is maximal under subgraph inclusion among such subgraphs: it is not a proper subgraph of another connected subgraph of without a cut vertex.
Common mistake
(Maximal is not maximum)
Maximal means that the subgraph cannot be enlarged while retaining both properties; it does not mean that it has the largest number of vertices among all candidates. In a triangle with a pendant edge , the single edge with its endpoints is a block although it has fewer vertices than the triangle: any connected subgraph properly containing it also contains together with a neighbor among , and then is a cut vertex separating from that neighbor.
We include two small cases in this definition. A single edge with its two endpoints has no cut vertex, because deleting either endpoint leaves a one-vertex connected graph. An isolated vertex itself is a block.
Definition 9.1.3
(2-connected graph)
A graph is 2-connected when it has at least three vertices, is connected, and remains connected after deleting any one vertex.
Thus blocks with at least three vertices are 2-connected; the small blocks require their own conventions.
Every block is an induced subgraph on its vertex set. Indeed, adding a missing edge between two of its vertices preserves connectedness, both before and after any vertex deletion. A non-induced candidate would therefore not be maximal. Finiteness ensures that every connected cut-free subgraph can be extended to a maximal one: enlarge it while possible, and the process must stop. In particular, every edge belongs to some block.
Counterexample mode
Blocks do not partition the vertices
Let the edge sets of two triangles be and . Their union has cut vertex , so the union is not a block. The two triangles are its blocks and both contain . Forcing every vertex into only one piece would erase one attachment. By contrast, the edges will belong to exactly one block each.
Splitting at a cut vertex
The main proof uses a smaller graph, not an unproved picture of how blocks ought to fit together.
Theorem 9.1.4
(A cut vertex separates the block problem)
Suppose is connected and is a cut vertex. Let be the vertex sets of the components of , where , and set
Each is connected, has fewer vertices than , and has at least two vertices. The blocks of are exactly the blocks of these , with no block counted twice.
Proof
(Proof that blocks split at a cut vertex)
Each component has a neighbor of : otherwise connectedness of would fail. Hence is connected. The pieces share only , and no edge joins distinct .
Let be any connected subgraph with no cut vertex. If met two different , connectedness would force it to contain , while would contain vertices in those two components with no path between them. Then would be a cut vertex of , a contradiction. Thus lies in one ; the singleton lies in every piece but is maximal in none, since each piece has an edge incident with .
A block of is therefore contained in one piece and must be maximal there. Conversely, let be a block of . It has an edge, since is connected with at least two vertices. If a larger connected cut-free subgraph of contained , the preceding argument would place it in one piece. The edge of forces that piece to be , contradicting maximality there. Blocks from different pieces cannot coincide, again because each has an edge and the piece edge sets are disjoint.
Proof X-ray
Why maximality survives the split
Two steps carry the proof. The first is a separation step: a connected subgraph that meets two different components of must pass through , and then is a cut vertex of that subgraph. It uses that the are the components of , so no edge of joins two of them. Consequently every connected cut-free subgraph of lies inside a single piece .
The second is an identification step. Vertex sets of the pieces overlap at , so a vertex cannot say which piece a block belongs to; the edge sets, however, are disjoint. Every block of a piece has an edge, because each is connected with at least two vertices, and that edge pins any proposed enlargement to the same piece. Maximality in and maximality in are then compared inside one fixed piece, which closes both directions. The only subgraph lying in every piece is the singleton , and it is harmless because has a neighbor in every , so is never maximal. Without the separation step, a block of could a priori extend through into , and the recursive description would say nothing about the blocks of .
Build the incidence forest
Definition 9.1.5
(Block incidence graph)
The block incidence graph of is the bipartite graph with two different types of nodes: one node for every original vertex of , and one new node for every block. A vertex node is joined to a block node exactly when .
A vertex named in the original graph, if one existed, would still be a different node from a block node: the two types are kept distinct.
Theorem 9.1.6
(The block incidence forest)
The graph is a forest whose connected components correspond to those of . Every edge of belongs to exactly one block, and two distinct blocks share at most one vertex.
Proof
(Proof by splitting and gluing trees)
Work separately in each nonempty connected component of , and induct on its number of vertices. If it has no cut vertex, the entire component is its unique block. Its incidence graph is a star, hence a tree; the edge and intersection assertions also hold. This includes a one-vertex component.
Otherwise split at a cut vertex as above. Each smaller satisfies the induction hypothesis. The block lemma says that its blocks are precisely the blocks needed for , and different pieces share no edge and only the original vertex . Their incidence trees therefore share exactly the node . Gluing trees together at a single common node produces a tree: it is connected, and a simple cycle cannot leave one tree and return through the same shared node without repeating that node. Edge uniqueness holds inside each piece by induction and between pieces by their disjoint edge sets. Block intersections have size at most one inside each piece by induction and between pieces because their vertex sets meet only at . This proves all claims. For the empty graph, both the block collection and are empty.
Concept lensStructural
Blocks as classes of edges
Call two edges related when they are equal or lie on a common cycle. A cycle is connected and cut-free, so it lies in one block, and edge uniqueness puts related edges in the same block. Conversely, two edges of a 2-connected graph always lie on a common cycle, a standard fact not proved here. Hence the relation is an equivalence whose classes are exactly the edge sets of blocks with an edge; a bridge forms a class alone. Isolated vertices are the only blocks this edge description omits.
Definition 9.1.7
(Block–cut forest)
The block–cut forest of is the subgraph of induced by all block nodes and those original vertex nodes that belong to at least two blocks.
We next prove that these are exactly the cut vertices. The full incidence forest is convenient meanwhile because every possible path endpoint already has a node.
Read vertex failures from a unique path
For distinct vertices and another vertex , all in one component of , compare connectivity after deleting in the two graphs. A path in gives a walk in : replace each edge by , where is its unique block. Conversely, a path in alternates vertex and block nodes. Replace each segment by an – path inside avoiding . Such a path exists: if , use connectedness of ; if , use the absence of cut vertices in . The two distinct surviving endpoints ensure that is nonempty. Concatenation gives a walk in , from which repetitions can be removed.
Theorem 9.1.8
(A path certificate for every separating vertex)
Let be connected in , and let . Deleting separates from if and only if the original-vertex node lies on the unique – path in .
Proof
(Proof through the path correspondence)
If is outside the component containing , deleting it does not affect their connectivity, and its node is outside their incidence-tree path. Otherwise the preceding correspondence gives an – path in exactly when there is one in . In a tree, deleting a node separates two other nodes exactly when it lies on their unique path. Apply this in their component of .
This statement deliberately excludes deleting an endpoint: removing does not leave a pair of surviving vertices whose connectivity can be tested. It also assumes that were connected before the deletion.
For a non-isolated vertex , each branch of in its original tree contains a surviving original vertex. Indeed, the first node in that branch is a block containing ; that block has at least two vertices, and another member lies in the branch. The same path correspondence therefore gives exactly components from the original component after deletion. Consequently
Common mistake
(A cut vertex need not split its component into two)
Deleting a cut vertex can produce more than two new pieces. The formula counts them: in the star the center lies in three bridge blocks, so and deleting it leaves three isolated vertices, an increase of two components. Reading “cut vertex” as “splits into exactly two parts” undercounts, and the same error appears when counting the components left by a vertex in four blocks.
Thus a vertex is a cut vertex exactly when it belongs to at least two blocks. An isolated vertex belongs to its singleton block, but deleting it gives , so it is not a cut vertex. Removing the other original vertex nodes from removes leaves only. This proves that the compact block–cut graph really is a forest, with one tree per original component; a component without a cut vertex becomes a single block node.
Three examples to compare
Worked example 9.1.9
(A bridge forest misses the shared vertex)
For triangles and , the full incidence tree has a path and leaves . The compact tree is . Hence is the only vertex other than whose deletion separates from . Every edge is on a triangle, so there are no bridges and the bridge forest has just one node. There is no contradiction: its nodes represent resilience to edge failure, whereas blocks concern vertex failure.
Worked example 9.1.10
(Triangles, a tail and an isolated vertex)
Take triangles , edges , and isolated vertex . The blocks have vertex sets . The nontrivial compact tree is
with a separate node for . Therefore the vertices separating from are exactly . Deleting leaves three components overall: , and . The two blocks containing give , so the formula gives . Deleting instead reduces the count from two to one; this is the isolated-vertex exception.
Worked example 9.1.11
(Two overlapping cycles need not be two blocks)
Take triangles and , sharing edge . The whole four-vertex graph has no cut vertex. Deleting or leaves a triangle; deleting leaves path ; deleting leaves path . Thus the whole graph is one block, not two triangle blocks. Each triangle is cut-free but fails maximality. Two genuine distinct blocks cannot share an edge or even two vertices.
Counts and a finite construction
Let , , , and let there be blocks. The full incidence forest has nodes, components and edges. The forest edge formula gives
The second equality follows from edge uniqueness. In the tail example the first sum is and the second is . These are useful checks on a proposed list, but numerical agreement alone does not prove that its pieces are maximal or cut-free.
The proof also supplies a finite procedure: process each component; if it has no cut vertex, output it; otherwise split at one cut vertex and recurse on the induced pieces. Each child has fewer vertices, so recursion stops. Record the original vertex labels, since a cut vertex is intentionally copied into several recursive pieces. One may find cut vertices by the earlier DFS test. This description proves a correct construction but does not establish a linear bound for repeatedly searching overlapping pieces; a dedicated edge-stack implementation requires its own analysis.
Practice with solutions
Quick check
(Find all blocks of the path . Which vertices separate from ?)
Test whether two consecutive edges can lie in one cut-free connected subgraph.
Solution · Answer
Each edge is a block. Any connected subgraph containing two consecutive edges has their shared vertex as a cut vertex, so it cannot be a larger block. The compact tree is . Exactly separate the endpoints.
Quick check
(A connected graph with at least two vertices has a vertex in four blocks. How many components remain after deleting it? What if two other connected components were present initially?)
Use the degree formula for the incidence forest.
Solution · Answer
The incidence degree is four, so its original component splits into four pieces. In the disconnected case the two other components survive, giving six components in total. The increase is three in either case.
Quick check
(Prove that a two-vertex block is exactly a bridge with its endpoints.)
Argue both directions: an edge that is not a bridge lies on a cycle, and a bridge inside a larger block creates a cut vertex.
Solution · Answer
Such a block consists of its one edge . If were not a bridge, a – path avoiding it together with would form a cycle. A cycle has no cut vertex and would enlarge the candidate, a contradiction. Conversely, a bridge belongs to some block. A connected cut-free graph with at least three vertices cannot contain a bridge: deleting the bridge partitions its vertices into nonempty sides; if one side has at least two vertices, deleting its endpoint of the bridge separates a vertex on that side from the other side. At least one side has two vertices. Thus the block containing the bridge has exactly its two endpoints.
Quick check
(A connected graph has four blocks of orders . Find its order. Can its number of edges also be determined?)
Use the forest count for .
Solution · Answer
The count gives , so . The edge count is not fixed: the order-four block could be a four-cycle with four edges or a complete graph with six edges. Attach a triangle and two bridge blocks in the same pattern in both constructions. All remain valid blocks, but the total edge counts differ by two.
Quick check
(Let be distinct vertices that are initially connected. Can they both belong to each of two different blocks? Can they stay connected after deleting every other individual vertex without belonging to any common block?)
Look at the internal nodes of the – path in .
Solution · Answer
The first answer is no: distinct blocks share at most one vertex. For the second, assume the pair is initially connected. If their incidence path has an internal original vertex node, that vertex separates them. If it has none, the path has the form , so they belong to a common block. Therefore the stated single-vertex resilience implies a common block. An adjacent pair may share a bridge block: deleting other vertices never removes their edge, so the statement does not imply two internally vertex-disjoint paths for adjacent endpoints.