Block-cutvertex tree terminology

PDF p. 3: Section 3, independent-set paragraph

Let $G$ be a finite connected simple graph with at least one edge. A cutvertex is a vertex whose deletion, together with its incident edges, increases the number of connected components. A block is a maximal 2-connected subgraph, or the subgraph consisting of a bridge and its two endpoints. Here 2-connected means connected, having at least three vertices, and remaining connected after deletion of any one vertex; a bridge is an edge whose deletion increases the number of connected components.

The block-cutvertex tree of $G$ is the incidence graph with one formally labelled node for each block and one differently labelled node for each cutvertex. A block node and a cutvertex node are adjacent exactly when the cutvertex belongs to that block; there are no other edges. A tree is a connected graph with no cycle.

Choose a block node as the root block. The distance of a node from the root is the number of edges in the unique path joining them. To process blocks away from the root, process their nodes in nondecreasing distance from the root, with ties in any order. For a nonroot block $B$, its attachment vertex is the cutvertex of $G$ represented by the node immediately following $B$ on the unique path from $B$ to the root. If there is only one block, it is the root and there are no nonroot blocks or attachment vertices.

Blocks and the parameter beta

Cutvertices, 2-connected pieces and nontrivial blocks

Block incidence tree and containment contract

Cycles, trees and forests in a simple graph on an arbitrary vertex set

A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path

The block and cutvertex definitions determine the two finite node families and the incidence relation. The graph has an edge, so it has a block. The block-incidence decomposition states that this incidence graph is a tree under the stated hypotheses. Formal labels keep the two node types distinct.

In a tree, each pair of nodes is joined by a unique path. Thus distances and the prescribed ordering are definite. A nonroot block node has a first neighbour on its path to the root; the incidence graph is bipartite, so that neighbour is a cutvertex node, and its associated vertex is uniquely determined. The one-block case has no nonroot block to which this prescription must be applied.

The article uses the root and attachment terminology in its greedy prescription. The explicit incidence construction and the choice of nondecreasing distance formalize that usage; the structural tree assertion is supplied independently by the block-incidence decomposition.