Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# networkx.algorithms.components.is_biconnected¶

is_biconnected(G)[source]

Returns True if the graph is biconnected, False otherwise.

A graph is biconnected if, and only if, it cannot be disconnected by removing only one node (and all edges incident on that node). If removing a node increases the number of disconnected components in the graph, that node is called an articulation point, or cut vertex. A biconnected graph has no articulation points.

Parameters: G (NetworkX Graph) – An undirected graph. biconnected – True if the graph is biconnected, False otherwise. bool NetworkXNotImplemented : – If the input graph is not undirected.

Examples

>>> G = nx.path_graph(4)
>>> print(nx.is_biconnected(G))
False

The algorithm to find articulation points and biconnected components is implemented using a non-recursive depth-first-search (DFS) that keeps track of the highest level that back edges reach in the DFS tree. A node n is an articulation point if, and only if, there exists a subtree rooted at n such that there is no back edge from any successor of n that links to a predecessor of n in the DFS tree. By keeping track of all the edges traversed by the DFS we can obtain the biconnected components because all edges of a bicomponent will be traversed consecutively between articulation points.