Why the Block-Cut Graph Is a Tree

Why Incidence Produces a Tree

A connected graph can contain several robust pieces joined at vertices whose deletion disconnects the graph. Blocks record those pieces, while cut vertices record where they meet. The block-cut incidence graph turns this arrangement into a simpler graph: its vertices represent blocks and cut vertices, and its edges record membership. The key fact is that this incidence graph is a tree when the original graph is connected. We will prove both connectedness and absence of cycles, including the cases involving bridges and a graph with just one vertex.

All graphs here are finite and simple. A graph is connected if every pair of its vertices is joined by a path. For any graph \(H\), let \(c(H)\) denote its number of connected components, with \(c(H)=0\) when \(H\) has no vertices. A vertex \(x\) is a cut vertex if \(c(G-x)>c(G)\). In a connected graph this is equivalent to saying that deleting \(x\) disconnects the graph. The component-count definition matters for disconnected graphs: deleting a vertex from one component does not make it a cut vertex merely because other components remain.

A bridge is an edge whose deletion increases the number of connected components. Including each bridge as a block is necessary: a bridge is not part of a 2-connected subgraph, but it is still part of the graph’s block structure. For a connected graph with a single vertex, the convention gives one block node and no cut-vertex nodes.

How Blocks Can Meet

We first establish the structural facts used in the tree proof. Two 2-connected subgraphs that share at least two vertices have a 2-connected union. Indeed, after deleting any vertex, at least one of their two shared vertices remains, so the two remaining subgraphs are connected and still meet. Their union is connected after that deletion and has at least three vertices.

Proof. Two distinct maximal 2-connected subgraphs cannot share two vertices: their union would be 2-connected by the preceding argument, contradicting maximality. A bridge block cannot share both endpoints with a 2-connected block, since then its edge would lie in a 2-connected subgraph and would not be a bridge. Two distinct bridge blocks in a simple graph cannot share both endpoints, because there is at most one edge with those endpoints. Thus distinct blocks meet in at most one vertex.

Now suppose distinct blocks \(B_1,B_2\) share a vertex \(x\), and suppose, for contradiction, that \(x\) is not a cut vertex. Since \(G\) is connected, \(G-x\) is connected. The sets \(V(B_1)\setminus\{x\}\) and \(V(B_2)\setminus\{x\}\) are nonempty and disjoint. Choose a shortest path \(P\) in \(G-x\) joining these sets. Its endpoints lie in the two respective sets, and no internal vertex lies in either set; otherwise a shorter such path could be chosen. Consider \(H=B_1\cup B_2\cup P\). If \(x\) is deleted from \(H\), the remaining parts of both blocks are connected and joined by \(P\). If a vertex \(z\neq x\) is deleted, each block with \(z\) removed is connected (a bridge block leaves either an edge or a single vertex), and the two remaining blocks still meet at \(x\). Any surviving pieces of \(P-z\) attach to one of its endpoints, so \(H-z\) is connected as well. Thus \(H\) is 2-connected. It properly extends each of the distinct blocks, contradicting maximality; if either block is a bridge block, its edge is contained in a 2-connected subgraph, contradicting that it is a bridge. Therefore \(x\) is a cut vertex. \(\square\)

Every edge of a connected graph with at least two vertices belongs to a block. A bridge belongs to its bridge block. A non-bridge edge lies on a cycle: its endpoints are still joined after the edge is deleted, and a shortest such alternate path together with the edge gives a cycle. A cycle is 2-connected, so, because the graph is finite, it is contained in a maximal 2-connected subgraph. An isolated vertex is covered by the singleton-block convention.

The Block-Cut Incidence Graph Is Connected

Proof. If \(G\) has a single vertex, \(BC(G)\) has just its one block node and is connected. Otherwise, take any two block nodes \(B\) and \(C\). Choose \(u\in V(B)\) and \(v\in V(C)\), and take a path in \(G\) from \(u\) to \(v\). Each edge of that path belongs to a block. Consecutive edge-blocks either are the same block or contain the common vertex of the consecutive edges. If they are distinct, the lemma says that this shared vertex is a cut vertex, so their nodes are joined through its node in \(BC(G)\). The first edge-block can likewise be connected to \(B\) through \(u\) if it differs from \(B\); the last can be connected to \(C\) through \(v\). If \(u=v\), distinct \(B\) and \(C\) are joined through their shared cut vertex by the lemma. Hence any two block nodes are connected in \(BC(G)\). Every cut-vertex node belongs to at least one block, so it is adjacent to a block node. Therefore the whole incidence graph is connected. \(\square\)

For completeness, every cut vertex is in at least two blocks. If \(x\) is a cut vertex of connected \(G\), each component of \(G-x\) contains a neighbor of \(x\); otherwise that component would have had no connection to \(x\) in \(G\). Choose one edge from \(x\) into each of two different components. Their blocks must be distinct: a 2-connected block remains connected after \(x\) is deleted, and a bridge block with \(x\) deleted leaves only one vertex. Neither can contain vertices in two different components of \(G-x\). This also confirms that every cut-vertex node has incident edges.

Why the Incidence Graph Has No Cycle

Proof. Suppose \(BC(G)\) contains a cycle. Since it is bipartite, the cycle alternates between block nodes and cut-vertex nodes. Write its distinct block nodes in cyclic order as \(B_1,\ldots,B_k\), and write \(x_i\) for the cut vertex shared by \(B_i\) and \(B_{i+1}\), where \(B_{k+1}=B_1\). The vertices \(x_1,\ldots,x_k\) are distinct. The lemma implies \(k\geq 3\): if \(k=2\), the two distinct blocks would share both \(x_1\) and \(x_2\).

Let \(H\) be the union of these blocks. Each block is connected, and the blocks meet in the cyclic pattern specified by the \(x_i\). We show that deleting any vertex \(z\) from \(H\) leaves a connected graph. Within each block, deleting \(z\) leaves a connected, nonempty subgraph: this follows from 2-connectivity for a 2-connected block, and a bridge block leaves a single vertex if one of its endpoints is deleted. If \(z\) is one of the connecting vertices \(x_i\), the cyclic chain of blocks remains joined by all the other connecting vertices; if \(z\) is not one of them, all the connections in the cycle remain. Thus \(H-z\) is connected in either case. Since the cycle uses at least three distinct blocks and connecting vertices, \(H\) has at least three vertices. Hence \(H\) is 2-connected.

But \(H\) contains distinct blocks and extends each of them, contrary to maximality of any 2-connected block in the cycle. If one of the blocks is a bridge block, its edge lies in the 2-connected subgraph \(H\), which contradicts that it is a bridge. Therefore \(BC(G)\) has no cycle. We have already proved that it is connected, so it is a tree. \(\square\)

Disconnected Graphs Give a Forest

Proof. Apply the connected-graph theorem separately to each connected component of \(G\). Blocks and cut vertices lie within individual components, so there are no incidence edges between the resulting incidence graphs. Each component’s incidence graph is a tree, including the one-node tree for an isolated vertex. Their disjoint union has no cycle and is therefore a forest. \(\square\)

Common Pitfall: What Counts as a Cut Vertex?

For a connected graph, saying “deletion disconnects the graph” is a convenient test for a cut vertex. It is not a safe definition for disconnected graphs. For example, let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,34\}\). Deleting vertex \(1\) leaves the edge \(34\) and the isolated vertex \(2\), so the result is disconnected. But \(c(G)=2\) and \(c(G-1)=2\); deletion did not increase the number of components. Thus \(1\) is not a cut vertex under the component-count definition. The same calculation applies to each vertex of this graph.

Using the broader but incorrect definition would add four cut-vertex nodes to the incidence graph of this example, even though no vertex joins different blocks. The correct definition \(c(G-x)>c(G)\) treats each connected component on its own and is consistent with the forest description.

The tree result also does not say that each block is a tree or that every vertex of the original graph is a cut vertex. A block may contain cycles, and vertices that are not cut vertices appear only inside block nodes. The tree records how the blocks are attached, not the internal edges of each block.