Bridge (graph Theory) - Bridgeless Graphs

Bridgeless Graphs

A bridgeless graph is a graph that does not have any bridges. Equivalent conditions are that each connected component of the graph has an open ear decomposition, that each connected component is 2-edge-connected, or (by Robbins' theorem) that every connected component has a strong orientation.

An important open problem involving bridges is the cycle double cover conjecture, due to Seymour and Szekeres (1978 and 1979, independently), which states that every bridgeless graph admits a set of simple cycles which contains each edge exactly twice.

Read more about this topic:  Bridge (graph Theory)