*** Welcome to piglix ***

Bridgeless graph


In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

Another meaning of "bridge" appears in the term bridge of a subgraph. If H is a subgraph of G, a bridge of H in G is a maximal subgraph of G that is not contained in H and is not separated by H.

A graph with nodes can contain at most bridges, since adding additional edges must create a cycle. The graphs with exactly bridges are exactly the trees, and the graphs in which every edge is a bridge are exactly the forests.


...
Wikipedia

...