Prove the following statement by prove its contrapostive For

Prove the following statement by prove its contrapostive. For a connected graph G, if an edge e belongs to every spanning tree of G, the G - e is not connected.

Solution

Suppose that e does not belong to every spanning tree of G. Let T be a spanning tree that does not contain e.

Then tree T is spanning subgraph of G-e.

If u and v are any 2 vertices of G -e, then there is a unique u-v path in T.

This is also u-v path in G-e.

Thus G-e is not connected and e is not a bridge.

Hence Proved