Question

Show that an edge with smallest weight in a connected weighted graph must be part of any minimum spanning tree.

Short answer

An edge with smallest weight has to be included in a minimum spanning tree.

Step-by-step solution

Definition

A graph is connected if there exists a path between every pair of vertices.

Kruskal's algorithm:

Start from a graph \({\bf{T}}\) that contains only the vertices and no edges.Repeatedly select the edge in the given graph \({\bf{G}}\) with the smallest weight (that doesn't cause a circuit) and add it to the graph \({\bf{T}}\).Once the graph is connected, we have found a minimum spanning tree.

Proof by contradiction

Given: \({\bf{G}}\) is a connected weighted graph

\({\bf{T}}\)is a minimum spanning tree of \({\bf{G}}\)

\({\bf{e}}\)is the edge with the smallest weight in \({\bf{G}}\)

To proof: \({\bf{T}}\) contains \({\bf{e}}\).

Let \({\bf{e}}\) not be included in \({\bf{T}}\) and let the weight of \({\bf{e}}\) be \({\bf{w}}\).

This then implies that the minimum spanning tree \({\bf{T}}\) contains only edges with weights larger than \({\bf{w}}\).

Weight of edge

This then implies that the minimum spanning tree\({\bf{T}}\)contains only edges with weights larger than w.

If we add \({\bf{e}}\) to \({\bf{T}}\), then the new graph \({\bf{T'}}\) will contains a simple circuit (which contains \({\bf{e}}\) ). If we then delete another edge \({\bf{f}}\) in the simple circuit, then the new graph \({\bf{T''}}\) will also be a spanning tree. Moreover, \({\bf{T''}}\) will have a smaller total weight than \({\bf{T}}\), since edge \({\bf{f}}\) has a larger weight than edge \({\bf{e}}\) (and the two trees only differ by these edges).

One has then obtained a contradiction (as \({\bf{T}}\) was the minimum spanning tree) and thus \({\bf{e}}\) has to be included in \({\bf{T}}\).