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.