graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a biconnected graph is a connected and "nonseparable"

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

, 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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

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 Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

(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 In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

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.

Structure of 2-connected graphs

Every 2-connected graph can be constructed inductively by adding paths to a

cycle Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in ...

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 nline 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.

External links

The tree of the biconnected components Java implementation
in the jBPT library (see BCTree class). Graph families Graph connectivity

Definition

Examples

Structure of 2-connected graphs

See also

References

External links