The Block-Cut Incidence Graph

From Blocks to an Incidence Graph

A graph can be assembled from pieces that meet at cut vertices. The block-cut incidence graph records just this information: one kind of node represents each block, another represents each cut vertex, and an edge records that a cut vertex belongs to a block. This representation makes the memberships visible without drawing the original graph again.

Throughout, graphs are finite and simple. Write $c(G)$ for the number of connected components of $G$, taking $c(G)=0$ when $V(G)=\varnothing$. A vertex $v$ is a cut vertex if $c(G-v)>c(G)$. A block is a maximal connected subgraph with no cut vertex, using the standard conventions that each bridge is a block consisting of its two endpoints and that an isolated vertex is a block by itself. Here, maximal means maximal under inclusion as a subgraph. These conventions let us include graphs with bridges and isolated vertices while retaining the usual blocks of size at least three.

Definition: Let $\mathcal{B}(G)$ be the set of blocks of $G$, and let $C(G)$ be its set of cut vertices. The block-cut incidence graph $I(G)$ has two disjoint classes of nodes: a block node $\beta_B$ for each $B\in\mathcal{B}(G)$, and a cut-vertex node $\gamma_v$ for each $v\in C(G)$. Its edge set is $$ E(I(G))=\{\beta_B\gamma_v:\ B\in\mathcal{B}(G),\ v\in C(G),\ v\in V(B)\}. $$

The labels $\beta_B$ and $\gamma_v$ are tagged: a block node and a cut-vertex node remain different kinds of objects even if their labels refer to the same part of the original graph. The incidence graph has no other nodes or edges. In particular, it does not copy the edges of $G$; its edges record block membership only. Since every incidence edge joins a block node to a cut-vertex node, the two node classes give a bipartition.

A Construction Procedure

Suppose the blocks and cut vertices have already been identified. To construct $I(G)$, first make one block node for every block and one cut-vertex node for every cut vertex. Then inspect each block: for every cut vertex that lies in it, add exactly one edge between the corresponding two nodes. A cut vertex in several blocks therefore gets several incident edges, while a block containing no cut vertex gets an isolated block node.

Make the node lists.
Write down all block nodes $\beta_B$ and all cut-vertex nodes $\gamma_v$ as separate lists.

Record memberships.
For each block $B$, list the cut vertices $v$ for which $v\in V(B)$.

Add one edge per membership.
For every listed pair $(B,v)$, add $\beta_B\gamma_v$. Do not add edges within either node class.

Check the result.
Count the membership pairs and compare that total with the number of incidence edges. Check each node’s degree against its membership list.

Proposition: In $I(G)$, the degree of $\beta_B$ is the number of cut vertices contained in $B$, and the degree of $\gamma_v$ is the number of blocks containing $v$.

Proof. By definition, the edges incident with $\beta_B$ are precisely the edges $\beta_B\gamma_v$ for cut vertices $v\in V(B)$. There is one such edge for each of those vertices, so $\deg_{I(G)}(\beta_B)$ is their number. Likewise, the edges incident with $\gamma_v$ are precisely the edges $\beta_B\gamma_v$ for blocks $B$ containing $v$, one for each such block. Thus $\deg_{I(G)}(\gamma_v)$ is the number of blocks containing $v$. $\square$

Counting identity: The number of edges of $I(G)$ is the total number of block–cut-vertex memberships: $$ |E(I(G))| =\sum_{B\in\mathcal{B}(G)}|\{v\in C(G):v\in V(B)\}| =\sum_{v\in C(G)}|\{B\in\mathcal{B}(G):v\in V(B)\}|. $$

Proof. Consider the set of all pairs $(B,v)$ such that $B$ is a block, $v$ is a cut vertex, and $v\in V(B)$. Each such pair contributes exactly one edge $\beta_B\gamma_v$ to $I(G)$, and every edge of $I(G)$ arises from exactly one such pair. Counting these pairs by their block coordinate gives the first sum; counting them by their cut-vertex coordinate gives the second sum. Both counts therefore equal $|E(I(G))|$. $\square$

Worked Constructions

Worked Example: Three Cut Vertices and Six Incidences

Let $G$ have vertex set $V=\{a,b,c,x,y,z,w\}$ and edge set $E=\{ab,bx,xa,ac,cy,ya,bz,cw\}$. The triangles $a,b,x$ and $a,c,y$ meet at $a$; the edges $bz$ and $cw$ are pendant edges.

The blocks are $B_1=G[\{a,b,x\}]$, $B_2=G[\{a,c,y\}]$, $B_3=G[\{b,z\}]$, and $B_4=G[\{c,w\}]$. The cut vertices are $a,b,c$. Indeed, deleting $a$ separates the two triangle portions and their pendant edges; deleting $b$ separates $z$ from the rest; deleting $c$ separates $w$ from the rest. Deleting any of $x,y,z,w$ does not increase the number of components.

Now list the memberships. $B_1$ contains cut vertices $a,b$; $B_2$ contains $a,c$; $B_3$ contains $b$; and $B_4$ contains $c$. Thus the incidence edges are $ \beta_{B_1}\gamma_a,\ \beta_{B_1}\gamma_b,\ \beta_{B_2}\gamma_a,\ \beta_{B_2}\gamma_c,\ \beta_{B_3}\gamma_b,\ \beta_{B_4}\gamma_c $. There are six block nodes and cut-vertex memberships? More precisely, there are four block nodes and three cut-vertex nodes, and six incidence edges.

The block-node degrees are $2,2,1,1$, whose sum is $2+2+1+1=6$. The cut-vertex-node degrees are $2,2,2$, whose sum is $2+2+2=6$. Both degree sums equal the six listed memberships.

Check: The original edge count is $3+3+1+1=8$, matching the eight distinct edges in $E$. This edge count is separate from the incidence-edge count: the incidence graph has six edges because there are six block–cut-vertex memberships.

Worked Example: A Chain of Two Triangles and a Bridge

Let $G$ have $V=\{a,b,c,d,e,f\}$ and $E=\{ab,bc,ca,cd,de,ec,ef\}$. Its blocks are the triangle $B_1=G[\{a,b,c\}]$, the triangle $B_2=G[\{c,d,e\}]$, and the bridge block $B_3=G[\{e,f\}]$.

The cut vertices are $c$ and $e$. Deleting $c$ separates the first triangle from the vertices $d,e,f$, while deleting $e$ separates $f$ from the rest. Deleting any other vertex leaves the remaining graph connected. The memberships are: $B_1$ contains $c$, $B_2$ contains $c,e$, and $B_3$ contains $e$.

Therefore $I(G)$ has nodes $\beta_{B_1},\beta_{B_2},\beta_{B_3},\gamma_c,\gamma_e$ and edges $\beta_{B_1}\gamma_c,\beta_{B_2}\gamma_c,\beta_{B_2}\gamma_e,\beta_{B_3}\gamma_e$. The block-node degrees are $1,2,1$, with sum $1+2+1=4$. The cut-vertex-node degrees are $2,2$, with sum $2+2=4$. Hence the membership count and the edge count are both four.

Check: The three blocks contain $3,3,1$ original edges, respectively, so their total is $3+3+1=7$, equal to $|E|=7$. The incidence graph has four edges, not seven: it records memberships rather than original edges.

Worked Example: Disconnected Graph with an Isolated Vertex

Let $G$ have $V=\{a,b,c,d,u,v,w,z\}$ and $E=\{ab,ac,ad,bc,bd,cd,uv,vw\}$. One component is the complete graph on $\{a,b,c,d\}$, another is the path $u,v,w$, and $z$ is isolated.

The blocks are $B_1=G[\{a,b,c,d\}]$, the bridge block $B_2=G[\{u,v\}]$, the bridge block $B_3=G[\{v,w\}]$, and the singleton block $B_4=G[\{z\}]$. The only cut vertex is $v$: deleting it separates $u$ and $w$, whereas deleting a vertex of the complete-graph component leaves that component connected, and deleting $z$ merely removes an isolated component. Thus $C(G)=\{v\}$.

Only $B_2$ and $B_3$ contain $v$, so $I(G)$ has the single cut-vertex node $\gamma_v$, four block nodes, and edges $\beta_{B_2}\gamma_v$ and $\beta_{B_3}\gamma_v$. The degrees of the four block nodes are $0,1,1,0$, summing to $0+1+1+0=2$; the cut-vertex-node degree is $2$. The block nodes for $B_1$ and $B_4$ are isolated in the incidence graph.

Check: The complete graph contributes six original edges, since its four vertices give the pairs $ab,ac,ad,bc,bd,cd$; the path contributes two, $uv,vw$; and $z$ contributes none. Thus $|E(G)|=6+2=8$, as listed, while $|E(I(G))|=2$, the number of memberships involving $v$.

Common Pitfalls

Do not confuse block edges with incidence edges. The edges of $G$ belong to its blocks, but they are not copied into $I(G)$. In the first example, a mistaken count might add only the two memberships for $B_1$, the two for $B_2$, and one for each pendant block, but then report five after overlooking that $B_4$ contains $c$. The correction is to list every block’s cut vertices: $B_1:\{a,b\}$, $B_2:\{a,c\}$, $B_3:\{b\}$, $B_4:\{c\}$. The counts are $2+2+1+1=6$. Equivalently, the cut-vertex degrees are $2,2,2$, also totaling $6$.

Include every block node. A block with no cut vertex still contributes a node; it is simply isolated in $I(G)$. The same applies to a singleton block under the stated convention. Omitting such nodes changes the incidence graph, even though it does not change its edge set.

Use membership, not proximity. An incidence edge $\beta_B\gamma_v$ is present exactly when $v\in V(B)$. A cut vertex being near a block in a drawing, or connected to it by an edge of the original graph, is not by itself the rule. Check the block’s vertex set.

The incidence graph is therefore a compact record of which cut vertices occur in which blocks. Its node degrees provide a direct consistency check, and the double-counting identity verifies that no membership has been omitted or counted twice.

Check Your Understanding

For each question, distinguish the original graph’s edges from block–cut-vertex incidences.

If a block contains three cut vertices, what is the degree of its block node in $I(G)$? Explain from the definition.
A graph has blocks $B_1,B_2,B_3$, and its cut vertices have memberships $B_1:\{x\}$, $B_2:\{x,y\}$, and $B_3:\{y\}$. List the incidence edges and compute the degree of each node.
Why does a block containing no cut vertex give an isolated node in the incidence graph?
A proposed incidence graph has block-node degrees $1,2,1$ and cut-vertex-node degrees $2,2$. Use the counting identity to determine its number of edges.
Under the stated convention, what node and edges does an isolated vertex of the original graph contribute to the block-cut incidence graph?

What You'll Learn