Minimum spanning tree

In graph theory, the minimum spanning tree (MST) problem finds a spanning tree (i.e., of all vertices) in a graph with the minimum weight. Formally, we’re given a positive weighted connected undirected graph $G=(V,E)$. We must find an MST $T$ such that:

$$w(T)=\min \sum _{(u,v)\in T}w(u,v)$$

Some algorithms that solve the MST problem:

• Kruskal’s algorithm
• Prim’s algorithm

Solution formulation

We can use a generic greedy approach to solve the MST problem, by assuming $T_p^{\text{optimal}}$ is part of an MST. We define a few terms:

• Safe edge — an edge that can be added to $T_p^{\text{opt}}$ and bring us one step closer to the final MST.
• Cut in $G$ — a partition of $V$ into $V_1$ and $V_2$ such that $V_1\cap V_2=\varnothing$ and $V_1\cup V_2=V$.
• Edge crossing the cut — an edge $(u,v)\in E$ such that $u\in V_1$ and $v\in V_2$.
• Light edge crossing a cut — is the minimum weight edge crossing the cut.

Then,