Algorithm: Prim's MST Input : G, a connected, weighted, undirected graph with n vertices and e edges r, a vertex in G Output: T a minimum weight spanning tree for G 0. mark each vertex's parent as "unknown" except r, which has parent nil ← i.e. only r is in the current MST 1. select vertex v with parent "unknown" with edge (u,v), where u's parent is not "unknown", such that (u,v) has minimum weight amongst all such edges 2. set v's parent to u ← i.e. add v to thecurrent MST by connecting it to u 3. goto Step 1
Theorem: If $T'$ is a subtree of a minimum spanning tree
for $G$, then there is a complete minimum spanning tree for
$G$, call it $T$, that contains $T'$ and contains the edge $(u,v)$
that is the minimum weight edge from a vertex in $T'$ to a
vertex not in $T'$.
Proof: Let $T^*$ be a spanning tree that contains $T'$ but does not contain the edge $(u,v)$. We will show how to "repair" it to create a tree that still contains $T'$, but also contains $(u,v)$, without increasing the total weight of the resulting tree. The unique path from $u$ to $v$ in $T^*$ leaves $T'$ along some edge $(y,z)$, i.e. $y$ is in $T'$, but $z$ is not. If we delete $(y,z)$ we have two disconnected trees, the one containing $u$ and the one containing $v$. If we then add the edge $(u,v)$, we reconnect the two trees, resulting in a new spanning tree, call it $T$. Since the weight of $(u,v)$ $\le$ the weight of $(y,z)$, the overall weight of $T$ is $\le$ the overall weight of $T^*$.
Second, we have to prove that finding an optimum solution to the smaller subproblem yields an optimum solution to the original problem. At first this is a bit confusing, because the way we've phrased Prim's algorithm, it's not clear that we have a "smaller problem of the same kind" to solve. So let's imagine specifying the problem Prim's algorithm is solving in a slightly different way:
Problem: Minimum Weighted Spanning Tree (containing proscribed subtree) Given: a connected Graph G (V is the set of vertices, E the set of edges) a subtree T' of G spanning the vertex set R, which is a subset of V Find : a spanning tree T of the graph G that contains T' as a subtree and has minimum weight over all such spanning trees.Hopefully you see that Prim's algorithm can be viewed as solving a sequence of such problems, where $|V-R|$ gets smaller at each step. Now what we have to prove is trivial, because a solution to the "smaller sub-problem" is a solution to the original problem, and therefore finding an optimal solution to the smaller subproblem is indeed the right thing to do.