# 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

• An edge is a bridge if and only if it is not contained in any cycle.

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

@Wiki

• Restating a lot of well-known results without proof does not help towards a proof of the OP's (extremely) simple result. – almagest Apr 20 '16 at 8:04

Let $$G$$ be a tree, and suppose that one of its edges $$\{v,w\}$$ is not a bridge. This implies that removing this edge does not disconnect $$G$$, i.e., if $$G'$$ is the graph $$G$$ with $$\{v,w\}$$ removed, $$G'$$ is connected. Hence, there exists a path connecting vertices $$v$$ and $$w$$ in $$G'$$. This path together with $$\{v,w\}$$ forms a cycle in $$G$$, which contradicts the assumption that $$G$$ is a tree. Therefore, every edge in $$G$$ must be a bridge.