TOPICS
Search

Biconnected Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A biconnected graph is a connected graph on at least three vertices having no articulation vertices (Skiena 1990, p. 175). Equivalently, it is a graph G having vertex connectivity kappa(G)>=2. The minimum-order convention excludes the one-vertex graph and the two-vertex path, even though neither has an articulation vertex.

BiconnectedGraphs

The numbers of biconnected simple graphs on n=1, 2, ... nodes are 0, 0, 1, 3, 10, 56, 468, ... (cf. OEIS A002218). The first few of these are illustrated above.

A block of a graph is a maximal connected subgraph having no articulation vertex (Harary 1994, p. 26; West 2000, p. 155). Blocks include isolated vertices, bridges, and maximal biconnected subgraphs. A connected graph consisting of a single block is also called a nonseparable graph. Such a graph is biconnected when it has at least three vertices.

NotBiconnectedGraph

A number of graphs that are connected but not biconnected are illustrated above. For graphs on at least two vertices, these are precisely the 1-connected graphs. Including the one-vertex graph, the numbers of connected but non-biconnected graphs for n=1, 2, ... are 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] >1. A collection of biconnected graphs is available using GraphData["Biconnected"].

Any graph containing a node of degree 1 cannot be biconnected. All Hamiltonian graphs on at least three vertices are biconnected (Skiena 1990, p. 177), but the converse is not necessarily so. Deleting any vertex of a Hamiltonian cycle leaves a path spanning the remaining vertices, so no articulation vertex is possible. A non-biconnected graph on at least two vertices is therefore nonhamiltonian. The singleton graph is Hamiltonian by convention. The following table summarizes some named graphs that are biconnected but non-Hamiltonian.

graph G|V(G)|
theta-0 graph7
Petersen graph10
Herschel graph11
first Blanuša snark18
second Blanuša snark18
flower snark J_520
Coxeter graph28
double star snark30
Thomassen graph34
Tutte graph46
Szekeres snark50
Meredith graph70

See also

Articulation Vertex, Block-Cut Tree, Connected Graph, Graph Block, k-Connected Graph, SPQR Tree

Explore with Wolfram|Alpha

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.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 155-158, 2000.Sloane, N. J. A. Sequences A002218/M2873 and A052442 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Biconnected Graph

Cite this as:

Weisstein, Eric W. "Biconnected Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BiconnectedGraph.html

Subject classifications