Biconnected graph
Type of graph
title: "Biconnected graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-families", "graph-connectivity"] description: "Type of graph" topic_path: "general/graph-families" source: "https://en.wikipedia.org/wiki/Biconnected_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Type of graph ::
In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.
The property of being 2-connected is equivalent to biconnectivity, except that the complete graph of two vertices is usually not regarded as 2-connected.
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 its incident edges).
A biconnected directed graph is one such that for any two vertices v and w there are two directed paths from v to w which have no vertices in common other than v and w.
Examples
File:4 Node Biconnected.svg|A biconnected graph on four vertices and four edges File:4 Node Not-Biconnected.svg|A graph that is not biconnected. The removal of vertex x would disconnect the graph. File:5 Node Biconnected.svg|A biconnected graph on five vertices and six edges File:5 Node Not-Biconnected.svg|A graph that is not biconnected. The removal of vertex x would disconnect the graph.
::data[format=table title="Nonseparable (or 2-connected) graphs (or blocks) with n nodes {{OEIS|id=A002218}}"]
| Vertices | Number of Possibilities | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | ||||||||||||||||||||
| 1 | ||||||||||||||||||||
| 1 | ||||||||||||||||||||
| 3 | ||||||||||||||||||||
| 10 | ||||||||||||||||||||
| 56 | ||||||||||||||||||||
| 468 | ||||||||||||||||||||
| 7123 | ||||||||||||||||||||
| 194066 | ||||||||||||||||||||
| 9743542 | ||||||||||||||||||||
| 900969091 | ||||||||||||||||||||
| 153620333545 | ||||||||||||||||||||
| 48432939150704 | ||||||||||||||||||||
| 28361824488394169 | ||||||||||||||||||||
| 30995890806033380784 | ||||||||||||||||||||
| 63501635429109597504951 | ||||||||||||||||||||
| 244852079292073376010411280 | ||||||||||||||||||||
| 1783160594069429925952824734641 | ||||||||||||||||||||
| 24603887051350945867492816663958981 | ||||||||||||||||||||
| :: |
Structure of 2-connected graphs
Every 2-connected graph can be constructed inductively by adding paths to a cycle .
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: https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html
- {{citation | last = Diestel | first = Reinhard | author-link = Reinhard Diestel | edition = 5th | isbn = 978-3-662-53621-6 | location = Berlin, New York | publisher = Springer-Verlag | title = Graph Theory | url = https://diestel-graph-theory.com/index.html | year = 2016}}.
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::