Blocks and the parameter beta

PDF p. 1: Section 2, first paragraph

Let $H$ be a finite simple graph with at least one vertex. A graph is connected if every two of its vertices are joined by a path; a component is a maximal connected subgraph. Deleting a vertex removes it and all incident edges; deleting an edge removes only that edge. A bridge is an edge whose deletion increases the number of components. A graph is 2-connected if it has at least three vertices, is connected, and remains connected after deletion of any one vertex.

A block of $H$ is either a 2-connected subgraph maximal under subgraph containment in $H$, or the two-vertex, one-edge subgraph consisting of a bridge and its endpoints. Isolated vertices are not blocks under this convention. The order $\mathrm{\mid }H\mathrm{\mid }$ is its number of vertices and the size $\mathrm{\parallel }H\mathrm{\parallel }$ is its number of edges. If $\mathrm{\parallel }H\mathrm{\parallel }\ge 1$, define $\beta (H)$ to be the largest order of a block of $H$; if $\mathrm{\parallel }H\mathrm{\parallel }=0$, define $\beta (H)=1$.

The graph conventions specify finite simple graphs and subgraph containment. The block-system definition specifies connectivity, deletion, bridges, 2-connected subgraphs and maximality, and proves that a finite graph with an edge has at least one nontrivial block. Its nontrivial blocks are exactly the blocks defined here, and its parameter $b(H)$ is their largest order when an edge exists and is $1$ otherwise. Thus $\beta (H)=b(H)$ is well-defined in both cases. The order and size notation is supplied by the graph-order definition. Graph and colouring conventions Cutvertices, 2-connected pieces and nontrivial blocks Order, size, complement and independence number