| | |
The following results will help us prove that the output of Prim's Algorithm is guaranteed to be a minimal spanning tree:
Every tree with $n \gt 1$ vertices has a leaf (i.e., some vertex of degree 1).
Proof: Suppose not. Every vertex must have a path to every other vertex, so the degree of each vertex must be greater than 0. However, any vertex of degree 1 in a tree is a leaf, so the degree of each vertex must be minimally 2. Let $v_0$ be any vertex of the graph. Choose to follow one of its edges to some other vertex. Let us denote this other vertex by $v_1$. Having used only one of $v_1$'s edges and remembering that it has at least two, follow one of the remaining edges adjacent to $v_1$ to a third vertex -- which we will call $v_2$. Note that $v_2$ can't have been previously visited, as this would create a cycle -- and all trees are acyclic. Continue in a similar way, traveling an unused edge adjacent to $v_2$ to a vertex $v_3$; an unused edge adjacent to $v_3$ to a vertex $v_4$, and so on... Due to the degree of each vertex being 2 or more, a vertex $v_k$ not previously visited (as otherwise we again have a cycle) is guaranteed to exist. However, this is impossible as there are $n$ distinct vertices. Therefore, every tree with a finite number of vertices greater than one must have a leaf.
Every tree of $n$ vertices has $(n-1)$ edges
Proof: Proceed by induction on the number of vertices. Clearly the result is true for the degenerate tree of only one vertex and no edges, thereby establishing our basis case. Now, assume the result holds for any graph with $n=k$ vertices. We must show that it holds for any graph with $n=k+1$ vertices. Suppose $T$ is such a graph. Delete one of $T$'s leaves (we know there is at least one leaf by the preceding theorem). This results in a subtree $T'$ with one less edge and one less vertex. By the inductive hypothesis, $T'$ must have $(k-1)$ edges. Thus, $T$ must have had $(k-1) + 1 = (k+1) - 1$ edges. So the result holds for any graph with $n=k+1$ vertices. By the principle of mathematical induction, we conclude every tree of $n$ vertices has $(n-1)$ edges.
A connected graph with $n$ vertices and a cycle must have $n$ or more edges.
Proof: Let $G$ be a connected graph with $n$ vertices and a cycle $C$. Consider the effect of deleting one edge $e$ of $C$. Let us call the resulting graph $G'$. Given any two vertices $u$ and $v$ in $G'$, the connectedness of $G$ guarantees a path $P$ connecting them in $G$. If $P$ doesn't contain $e$, then $P$ also connects $u$ and $v$ in $G'$. If $P$ does contain $e$, then a new path $P'$ connecting $u$ and $v$ in $G'$ can be formed by replacing $e$ with a traversal of the remaining edges of $C$. Thus, $G'$ is connected. As such, $G'$ contains a minimal spanning tree $T$ of $(n-1)$ edges. Since the original graph $G$ has one more edge than $G'$, which in turn has at least as many edges as $T$, it must be the case that $G$ has at least $n$ edges.