## FANDOM

1,180 Pages

Prim's algorithm yields a minimal spanning tree.

## Proof

Let $T$ be the spanning tree on $G$ generated by Prim's algorithm, which must be proved to be minimal, and let $T'$ be spanning tree on $G$, which is known to be minimal.

If $T = T'$, then $T$ is minimal.

If $T \ne T'$, let $e_k = (u,v)$ be the first edge chosen by Prim's algorithm which is not in $T'$, chosen on the $k$'th iteration of Prim's algorithm. Let $P$ be the path from $u$ to $v$ in $T'$, and let $e*$ be an edge in $P$ such that one endpoint is in the tree generated at the $k-1$'th iteration of Prim's algorithm and the other is not, i.e., one endpoint of $e*$ is $u$ or one endpoint is $v$, but the endpoints are not $u$ and $v$.

If the weight of $e*$ is less than the weight of $e_k$, then Prim's algorithm would have chosen it on its $k$th iteration, so it is certain that $w(e*) \ge w(e_k)$. In particular, when $e*$ has weight equal to that of $e_k$, the choice between the two is arbitrary. Whether the weight of $e*$ is greater than or equal to $e_k$, $e*$ can be substituted with $e_k$ while preserving minimal total weight of $T'$. This process can be repeated indefinitely, until $T'$ is equal to $T$, and it is shown that the tree generated by any instance of Prim's algorithm is a minimal spanning tree.

QED

Community content is available under CC-BY-SA unless otherwise noted.