Biconnected Graph

A biconnected graph is a connected graph having no articulation vertices (Skiena 1990, p. 175). Biconnected graphs are also sometimes called blocks or nonseparable graphs (Harary 1994, p. 26). An equivalent definition for graphs on more than two vertices is a graph having vertex connectivity .

The cases of the singleton graph and path graph are somewhat problemetic. The singleton graph is "annoyingly inconsistent" (West 2000, p. 150) since it is connected (but 1-connected only; not 2-connected), but by convention it is taken to have . The path graph is also problematic, since it has no articulation vertices and for the purpose of theorems such as those involving unit-distance graphs, it is convenient to regard it as biconnected, yet it has vertex connectivity .

Some biconnected graphs are illustrated above. Taking and as not biconnected and biconnected, respectively gives the numbers of biconnected simple graphs on , 2, ... nodes as 0, 1, 1, 3, 10, 56, 468, ... (cf. OEIS A002218).

A number of graphs that are connected but not biconnected are illustrated above. Such graphs are called 1-connected, and the numbers of such graphs for , 2, ... are given by 1, 1, 1, 3, 11, 56, 385, ... (OEIS A052442).

A graph can be tested for biconnectivity in the Wolfram Language using KVertexConnectedGraphQ[g, 2] or VertexConnectivity[g] . A collection of biconnected graphs is available using GraphData["Biconnected].

Any graph containing a node of degree 1 cannot be biconnected. All Hamiltonian graphs are biconnected (Skiena 1990, p. 177), but the converse is not necessarily so. In particular, a non-biconnected graph is automatically non-Hamiltonian, which can be seen be noting that if removal of an articulation vertex left a Hamiltonian path, this would imply that disconnected graphs were connected. The following table summarizes some named graphs that are biconnected but non-Hamiltonian.

graph
theta-0 graph	7
Petersen graph	10
Herschel graph	11
first Blanuša snark	18
second Blanuša snark	18
flower snark	20
Coxeter graph	28
double star snark	30
Thomassen graph	34
Tutte's graph	46
Szekeres snark	50
Meredith graph	70

Wolfram Web Resources