A biconnected graph is a connected graph having no articulation vertices (Skiena 1990, p. 175). An equivalent definition for graphs on more than two vertices is a graph having vertex connectivity .
The numbers of biconnected simple graphs on , 2, ... nodes are 0, 0, 1, 3, 10, 56, 468, ... (cf. OEIS A002218). The first few of these are illustrated above.
Maximal connected graphs on two or more vertices are called blocks or nonseparable graphs (cf. Harary 1994, p. 26). Biconnected graphs are closely related to blocks. If a block has more than two vertices, then it is biconnected (West 2000, p. 155). Conversely, biconnected graphs on two or more vertices are blocks.
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 |