If a graph G contains a bridge e is it possible to construct

If a graph G contains a bridge, e, is it possible to construct a spanning tree which does not include this edge? Justify your answer.

Solution

we will use Contradiction proof. But before this I am going to use 2 theorem whose proof you can find in any book.

(Tree Cycle Theorem) Given a tree T the addition of any non-edge of T creates a cycle.

(Bridge Theorem) An edge of a graph G is a bridge if and only if it lies on no cycle of G.

Suppose that \"e\" was a bridge in a graph \"G\", and \"T\" a spanning tree which does not contain \"e\". The addition of \"e\" to \"T\" creates a cycle containing \"e\", by the Tree Cycle Theorem (Theorem 9). But this contradicts the Bridge Theorem . Hence contradiction. Get back to me if you need the proof of those theorems as well.