Bridge (graph theory)
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Bridge_(graph_theory)".

A graph with 6 bridges (highlighted in red)

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.

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.¹

See also

• Articulation vertex

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

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.