About Prim's Algorithm (Aho, Hopcroft, Ullman)

Question

After $i$ th step, we get a set of edges $\{(u_1, v_1), (u_2, v_2), \dots, (u_i, v_i)\}$ by Prim's Algorithm.
The MST Property guarantees that there is a minimum-cost spanning tree that includes $(u_i, v_i)$ as an edge.
But I don't think the MST Property guarantees that there is a minimum-cost spanning tree that includes a set of edges $\{(u_1, v_1), (u_2, v_2), \dots, (u_i, v_i)\}$.
Is it obvious that there is a minimum-cost spanning tree that includes a set of edges $\{(u_1, v_1), (u_2, v_2), \dots, (u_i, v_i)\}$ after $i$ th step?
Do we need a proof?
If so, please give me a proof.

Answer 1

It looks to me you're misunderstanding Prim's algorithm. At each step, it only adds ONE edge to the current tree. More fully, for a graph $G(V, E)$:

• Start with a single started vertex $v$. Let $U := \{v\}$.
• Consider all edges with one end in $U$, $T=\{u_i, v_i: u_i \in U, v_i \in V-U\}$.
• Add the smallest edge in $T, (u_1, v_1)$ to the current MST, and the vertex $v_1$ to $U$. Repeat from the previous step.

So, for the algorithm to work, you only need to be sure that $(u_1, v_1)$ is in the MST, not all the enges in $T$.