Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is the proof that was given in my textbook (P.178 of "Introduction to Combinatorics"). I want to check if my reasoning behind the parts in bold are correct.

Let $T_i$ be the tree obtained by the algorithm with $i$ vertices, $V_i$ be the vertex set for $T_i$, $y_i$ be the edge added in going from $T_{i-1}$ to $T_i$, and$c(y)$ be the cost of edge $y$.

The object is to prove that $T_v$ obtained by Prim's Algorithm is a minimal spanning tree.

Suppose $T^1$ is a minimal spanning tree in $G$. Find the smallest $i$ such that $y_i$ is not an edge of $T^1$. Since $T^1$ is a spanning tree of $G$, (1)there is a path in $T^1$ joining the two end points of $y_i$. (2)As one travels along the path, one must encounter an edge $z$ joining a vertex in $V_{i-1}$ to one that is not in $V_{i-1}$. Now, at the iteration when $y_i$ was added to $T_{i-1}$, $z$ could also have been added, (3)and it would have been added instead of $y_i$ if its cost was less than that of $y_i$. So (4)$c(z) \ge c(y_i)$. Then (5)$T^2$ is connected, (6)has the same number of edges as $T^1$, (7)and the total cost of its edges is not larger than that of $T^1$, therefore (4)it is also a minimum spanning of $G$ and (8)it contains $y_i$ and all the edges added before it during the construction of $T_v$. Repeat this process until $T_v$ is achieved.

(1)By definition, a spanning tree is a connected graph that includes all the vertices in $G$. Therefore, there is a walk between any two vertices of $G$, and any walk contains a path.

(2)Suppose there was no such edges. Then all the endpoints of the edges in the path would be in $V_{i-1}$, and it would be impossible for the walk to finish at the other endpoint, which is a vertex not in $V_{i-1}$.

(3)Because Prim's algorithm chooses the edge with the smallest cost that increases the number of vertices by one.

(4)This is more a question; why is it not $c(z) = c(y_i)$? Is it possible that $c(z) \gt c(y)$ and $T^1$ is still a minimum spanning tree?

(5)Let the two endpoints of $y_i$ be $a, b$ and those of $z$ be $x,y$. So the walk from $a$ to $b$ via edge $z$ is $aAxyBb$, whee $A$ and $B$ are strings of vertices. After deleting $z$, one can still go from $x$ to $y$ by way of $xAabBy$ (with the order of $B$ reversed). All other edges are unchanged and $T^1$ was connected, so the $T^2$ is connected.

(6)Because we deleted one edge and added another.

(7)The only change in the cost was replacing $c(z)$ with $c(y_i)$, of which the latter was less than or equal to the former.

(8)Suppose there was an edge $y_k$ with $k \lt i$ such that it is not in $T^2$. Then it is not in $T^1$, because this edge was unchanged. This contradicts the $y_i$ being the edge with the smallest $i$ that is not an edge in $T^1$.

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.