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

Question

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?

Answer 1

• 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

Answer 2

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.