1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @bof Sorry I will edit it $\endgroup$ – JAEMTO Apr 20 '16 at 6:37
  • $\begingroup$ @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. $\endgroup$ – almagest Apr 20 '16 at 6:38
  • $\begingroup$ @JAEMTO Your edit has not helped. A tree is not simply a graph with no cycle, it is a connected graph with no cycle! $\endgroup$ – almagest Apr 20 '16 at 6:52
  • 1
    $\begingroup$ @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? $\endgroup$ – almagest Apr 20 '16 at 7:32
  • 1
    $\begingroup$ @JAEMTO Well done! You have solved it. $\endgroup$ – almagest Apr 20 '16 at 7:53
1
$\begingroup$
  • 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

$\endgroup$
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.