Bridge (graph theory)
From Wikipedia, the free encyclopedia
In graph theory, a bridge (also known as a cut-edge or an isthmus) is an edge whose deletion increases the 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 if it contains no bridges. It easy to see that this is equivalent to 2-edge-connectivity.
An important open problem involving bridges is the so-called Cycle Double Cover Conjecture, due to Seymour and Szekeres (1978 and 1979, independently), which states that every bridgeless graph admits a set of cycles which contains each edge exactly twice.
.svg/30px-Encoder_Disc_(3-Bit).svg.png){kind=small}
