Editing Bridge (graph theory) (section)

==Trees and forests==
A graph with <math>n</math> nodes can contain at most <math>n-1</math> bridges, since adding additional edges must create a cycle. The graphs with exactly <math>n-1</math> bridges are exactly the [[tree (graph theory)|trees]], and the graphs in which every edge is a bridge are exactly the [[forest (graph theory)|forests]].

In every undirected graph, there is an [[equivalence relation]] on the vertices according to which two vertices are related to each other whenever there are two edge-disjoint paths connecting them. (Every vertex is related to itself via two length-zero paths, which are identical but nevertheless edge-disjoint.) The equivalence classes of this relation are called '''2-edge-connected components''', and the bridges of the graph are exactly the edges whose endpoints belong to different components. The '''bridge-block tree''' of the graph has a vertex for every nontrivial component and an edge for every bridge.<ref>{{citation
 | last1 = Westbrook | first1 = Jeffery | author1-link = Jeff Westbrook
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | doi = 10.1007/BF01758773
 | issue = 5–6
 | journal = Algorithmica
 | mr = 1154584
 | pages = 433–464
 | title = Maintaining bridge-connected and biconnected components on-line
 | volume = 7
 | year = 1992}}.</ref>