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 is easy to see that this is equivalent to 2-edge-connectivity of each component.

[edit] Cycle double cover conjecture

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 cycles which contains each edge exactly twice.^[1]

[edit] See also

• Articulation vertex

[edit] References

• Béla Bollobás, Modern graph theory, GTM 184, Springer Verlag, 1998. Page 6.

1. ^ http://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm