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?

@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

ArsenBerk · Accepted Answer · 2018-01-06 08:20:20Z

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.

ArsenBerk

12.5k3 gold badges18 silver badges44 bronze badges

answered Apr 20 '16 at 7:55

ً ً

4,53912 gold badges42 silver badges103 bronze badges

2

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

add a comment |

1 Answer 1