Question

Let e be the unique lightest edge in a graph G. Let T be a spanning tree of G such that e ∉ T . Prove using elementary properties of spanning trees (i.e. not the cut property) that T is not a minimum spanning tree of G.

Answer 1

Question : To prove that T is not a minimum spanning tree of G.

Solution : A spanning tree is a tree with V -1 edges. i.e ; a tree that connects all vertices.

A minimum spanning tree is a tree of minimum total weight.

Edge inclusion lemma :

Let S be a subset of V , and suppose e = ( U,V ) is the minimum cost edge of E , with U in S and V in V - S .

e is in every minimum spanning tree of G , if e is not in T then T is not a minimum spanning tree.

Proof :

Suppose T is a spanning tree that does not contain e

Add e to T , this creates a cycle .

The Cycle must have some edge e₁ = ( U₁ , V₁ ) with U₁ in S and V₁ in V - S .

T₁ = T - { e₁ } + {e} is a spanning tree with lower cost or a minimum spanning tree   

Hence T is not a minimum spanning tree , Since e is the unique lightest edge.