Biconnected graph

In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.

In other words, a biconnected graph is nonseparable, meaning if any vertex were to be removed, the graph will remain connected.

Biconnected is another way of saying the graph is a K-vertex-connected graph, where $K\; =\; 2$.

This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection).

The use of biconnected graphs is very important in the field of networking (see Network flow), because of this property of redundancy.

Definition

A biconnected undirected graph is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and incident edges).

A biconnected strongly connected directed graph $G$ is a set of vertices $V$ so that every vertex has at least two in-degree vertices, and at least two out-degree vertices; ie. there are at least two independent paths from any vertex to any other vertex.

Examples

* [http://mathworld.wolfram.com/images/eps-gif/BiconnectedGraphs_1000.gif]

References

* Eric W. Weisstein. "Biconnected Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BiconnectedGraph.html
* Paul E. Black, "biconnected graph", in Dictionary of Algorithms and Data Structures [online] , Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/biconnectedGraph.html