# How to prove that each edge of tree is a bridge?

How to prove that each edge of tree is a bridge?

My attempt:

Tree is a connected graph which has no cycle, and in a connected graph, bridge is an edge whose removal disconnects the graph.

Let G be a tree, and each edge of G is not a bridge.

I should find a contradiction from my assumption.

But, now I can't go proceed. I think by this way I can prove, and I can't express it.

How can I go further?

• @bof Sorry I will edit it – JAEMTO Apr 20 '16 at 6:37
• @bof I cannot see any ambiguity. A tree is a graph in which any two vertices are connected by exactly one path. A bridge is an edge whose removal increases the number of components. One can express the same ideas is slightly different ways of course, but the concepts are standard and well-established. – almagest Apr 20 '16 at 6:38
• @JAEMTO Your edit has not helped. A tree is not simply a graph with no cycle, it is a connected graph with no cycle! – almagest Apr 20 '16 at 6:52
• @JAEMTO Ok. Suppose there is an edge AB which is not a bridge. Then after removing it there is a path from A to B. That path cannot involve the edge AB because you have just removed it. So how does that give you a contradiction? – almagest Apr 20 '16 at 7:32
• @JAEMTO Well done! You have solved it. – almagest Apr 20 '16 at 7:53

• A tree has no simple cycles and has $(n − 1)$ edges.
• The graphs with exactly $(n-1)$ bridges are exactly the trees.
• A graph with $n$ nodes can contain at most $(n-1)$ bridges, since adding additional edges must create a cycle.