Subscribe to the weekly news from TrueShelf

## Minimum spanning trees

Suppose we are given a connected graph \(G\) with weights on edges, such that all edge weights are distinct.

For any cycle in \(G\), prove that the maximum weight edge in the cycle cannot be in any minimum spanning tree of \(G\).

For any subset \(S \subset V\), \(S \not = \emptyset\), we say that the subset of edges with one end point in \(S\) and the other in \(V \setminus S\) is a

**cut**in the graph and is denoted by \((S,\bar{S})\). Consider a cut \((S,\bar{S})\) in \(G\). Prove that the minimum weight edge in the cut must belong to every minimum spanning tree of \(G\).

**Source:**folklore