Biconnected Graph

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

REFERENCES

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Sloane, N. J. A. Sequences A002218/M2873 and A052442 in "The On-Line Encyclopedia of Integer Sequences."