Prim's Algorithm

A minimal spanning tree for a graph $G$ is an acyclic, connected subgraph of an edge-weighted graph $G$ that contains all of the vertices of $G$ and has minimal total edge-weight. Prim's algorithm provides an easy way to identify a minimal spanning tree for a connected, edge-weighted graph.

Prim's Algorithm

Start with any vertex as a single-vertex graph $T$.
Repeat the following until it is impossible to do so (i.e., when $T$ contains every vertex of $G$):
Add a minimum-weight edge that connects a vertex in $T$ to a vertex not yet in $T$.

If the graph $G$ contains $n$ vertices, then note that we end up adding precisely $(n-1)$ edges to $T$ (since exactly one new vertex is added to $T$ with each edge addition).

Proof that Prim's Algorithm Results in a Minimal Spanning Tree

Let $G$ be a connected, edge-weighted graph. Let us denote the vertex that we used to start Prime's algorithm as vertex $s$. Also, suppose we denote the graph produced by Prim's Algorithm as $Y$.

Consider the following claims, in order:

Claim: $Y$ spans $G$ (i.e., $Y$ contains all of the vertices of $G$)

Proof: Suppose $Y$ does not span $G$. Let us denote set of vertices of $G$ that are not in $Y$ by $X$. Since $Y$ does not span $G$, $X$ must be non-empty. Let us denote one of the elements of $X$ by $x$. Note, it must be case that it is impossible to find an edge that connects a vertex in $Y$ to one in $X$, as otherwise the algorithm could have continued instead of terminating with $Y$.

Recall $G$ is connected, so there is a path between any two of its vertices. Consider the path between $s$ and $x$. Since $s$ is in $Y$ and $x$ is in $X$, and no vertex of $G$ lies outside of both $Y$ and $X$, there must be some edge on this path with one vertex in $Y$ and the other in $X$. Contradiction. Therefore $Y$ must span $G$.

Claim: $Y$ is a tree (i.e., $Y$ is connected and acyclic)

Proof: As for the second claim, recall that at every iteration we add an edge with one vertex $x_k$ in a subgraph $T$ of $G$ and one vertex $x_{k+1}$ not in $T$. For each vertex $x_{k+1}$ so added, let us refer to the corresponding $x_k$ as the "parent" of $x_{k+1}$.

To argue the connectedness of $Y$, we merely need to show that any two vertices of $Y$ are connected by a path. Consider any vertex $x_n$ of $Y$ not identical to $s$. Let $x_{n-1}$ be the parent of $x$, $x_{n-2}$ be the parent of $x_{n-1}$, $x_{n-3}$ be the parent of $x_{n-2}$, and so on... This sequence describes a path that must terminate with $x_0 = s$. Since there is always a path from any vertex of $Y$ to $s$, there must be a path between any two vertices $x_n$ and $x_m$ of $Y$ (consider conjoining the path from $x_n$ to $s$ to the path from $s$ to $x_m$). Thus, $Y$ is connected. (Indeed -- the same argument tells us that each subgraph $T$ mentioned in the description of the algorithm above must also be connected.)

It remains to show that $Y$ is acyclic. Let us argue indirectly. Suppose there is a cycle $C$ in $Y$. Suppose the last edge of $C$ that is added in the construction of $Y$ connects vertices $c_1$ with $c_2$, where $c_1$ is the parent of $c_2$. So there is some subgraph $T$ of $G$ that contains all of the edges in cycle $C$ and the vertex $c_1$, but does not contain $c_2$. This is impossible, as every vertex in a cycle is adjacent to two edges in that cycle. The edge between $c_1$ and $c_2$ may be missing from $T$, but there is another edge in $C$ adjacent to $c_2$. Since this other edge is in $T$, $c_2$ must be in $T$ as well. Contradiction. Thus $Y$ is acyclic.

Claim: $Y$ is a minimal spanning tree

Proof: Let $Y_1$ be a minimal spanning tree of $G$. Certainly if $Y_1 = Y$, we are done. If not, our strategy will be to find some other minimal spanning tree $Y_n = Y$.

Suppose edge $e$ is the first edge added in the construction of $Y$ that is not in $Y_1$. Let $V$ be the vertices connected the moment before $e$ is added in the construction of $Y$. Further, suppose that $e$ connects vertices $u_e$ and $w_e$ where $u_e$ is the parent of $w_e$. As such, $u_e$ is in $V$, while $w_e$ is not in $V$. Recall, $Y_1$ is a spanning tree, so there must be a path $P$ from $u_e$ to $w_e$ in $Y_1$. Since $u_e$ is in $V$ and $w_e$ is not, there must be a first edge $f$ in this path $P$ with one vertex in $V$ and one vertex not in $V$. Note, when we added edge $e$ in the construction of $Y$, we could have added $f$ instead, but we didn't. As such, we know that if $$w(f) \ge w(e)$$

Construct a new graph, $Y_2$ from $Y_1$ by removing edge $f$ and replacing it with edge $e$. We claim this new graph must also be a spanning tree. To see this, consider the following:

$Y_2$ is connected, as any path between two vertices that required $e$ can use $f$ instead.
$Y_2$ must be acyclic, as $Y_2$ has the same number of edges as $Y_1$ -- one less than the number of vertices in $G$. (Note, a connected graph with a cycle must have a number of edges that equals or exceeds the number of vertices of that graph.)

Finally, upon noticing that $Y_2$ has no greater weight than $Y_1$, we see that $Y_2$ is a minimal spanning tree too. If $Y_2 = Y$, we are again done. If not, we proceed as above to produce minimal spanning trees $Y_3$, $Y_4$, etc. This process must terminate with some $Y_n = Y$ as we must eventually run out of edges $e$ that were added in the construction of $Y$, but that are not in $Y_i$. Thus $Y$ is a minimal spanning tree!