Question

Show that if \(G\) is a weighted graph with distinct edgeweights, then for every simple circuit of \(G\), the edge of maximum weight in this circuit does not belong to anyminimum spanning tree of \(G\).

Short answer

The edge of maximum weight in some circuit of a weighted graph cannot be included in the minimum spanning tree of the graph.

Step-by-step solution

Definition

A minimum spanning tree of a weighted graph \(G\) is a spanning tree of \(G\) with minimal weight.

Given: \(G\) is a connected undirected weighted graph

\(G\)has distinct edge weights

\(C\)is a simple circuit in \(G\)

\(T\) is a minimum spanning tree of \(G\)

Proof by contradiction

To proof: The edge of maximum weight in \(C\) does not belong to \(T\)

Let the edge of maximum weight in \(C\)be\({\bf{e = \{ u,v\} }}\)and let \(e\) belong to \(T\).

Let \({\bf{T' = T - \{ e\} }}\). \({\bf{T''}}\) is then a forest with \(2\) connected components.

Let \(f\) be the edge in the path \({\bf{C - \{ e\} }}\) that is used to "jump" between the \(2\) connected components (this edge has to exists, as \(C\) was a circuit). \(f\) is not an edge in \(T\) (because else \(T\) would contain a circuit).

Since \(e\) is the edge in \(C\) with maximum weight and since \(G\) has distinct edge weights, \(e\) has a larger weight than \(f\)

\(w(e){\bf{ > }}w(f)\)

Weight of edge

Let \(T''{\bf{ = }}T \cup \{ f\} {\bf{ - }}\{ e\} \), then the weight of \({\bf{T''}}\) is less than or equal to the weight of \(T\) since \(w(e){\bf{ > }}w(f)\)

\(w(T''){\bf{ < }}w(T)\)

Thus \({\bf{T''}}\) is then a spanning tree with a smaller weight than \(T\). However as \(T\) was the minimum spanning tree, there should not exist a spanning tree with a lower weight and thus we have derived a contradiction. This means that the assumption that \(e\) belongs to \(T\) was wrong (and thus \(e\) cannot belong to \(T\)).