[Math] How to prove that each edge of tree is a bridge

discrete mathematicsgraph theorytrees

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?

Best Answer

  • 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

Related Question