## 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

0

0

0

0

0

0

0

0

0

0