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

Related Content