Prove that an edge e of a connected graph G is a bridge if and only if e belongs to

Problem 4

Prove that an edge e of a connected graph G is a bridge if and only if e belongs to every spanning tree of G.

                                                             Step by Step Solution

Step 1 of 3

Case-1

Let if the  edge does not belong to every spanning tree of .

Let  be a spanning tree that does not contain .

Then the tree  is a spanning subgraph of .

If  and  are any two vertices of , then there is a unique  path exists in .

This is a  path in .

Therefore  is connected and is not a bridge.