Prims algorithm is another linear time algorithm that takes a weighted graph as an input and outputs a MST. The algorithm is

Step 1: Pick a vertex u and set X = {e₁} where w(e₁) = min{w(e), e = (uv) E} is an edge of minimun weight adjacent to u.

Step 2: While |X|

This problem shows that Prims algorithm outputs a MST using the cut property from class. (see picture below for cut property)

a) Given the set X of edges at a given time, define the set of vertices S you will apply the cut property to.

b) Explain why for your choice of S, Prims algorithm will add next an edge in cut(S, S).

c) Conclude, invoking the cut property, that the resulting tree is a MST.

5.1.2 The cut property Say that in the process of building a minimum spanning tree (MST), we have already chosen some edges and are so far on the right track. Which edge should we add next? The following lemma gives us a lot of flexibility in our choice. Cut property Suppose edges X are part of a minimum spanning tree ofG = (V. E). Pick any subset of nodes S for which X does not cross between S and V - S, and let e be the lightest edge across this partition. Then X U {e} is part of some MST A cut is any partition of the vertices into two groups, S and V- S. What this property says is that it is always safe to add the lightest edge across any cut (that is, between a vertex in S and one in V - S), provided X has no edges across the cut. Let's see why this holds. Edges X are part of some MST T; if the new edge e also happens to be part of T, then there is nothing to prove. So assume e is not in T. We will construct a different MST T, containing X U {e} by altering T slightly, changing just one of its edges. Add edge e to T. Since T is connected, it already has a path between the endpoints of e, so adding e creates a cycle. This cycle must also have some other edge e' across the cut (S, V - S) (Figure 8.3). If we now remove this edge, we are left with T TUe) - fe'), which we will show to be a tree. T' is connected by Property 1, since e' is a cycle edge. And it has the same number of edges as T; so by Properties 2 and 3, it is also a tree. Moreover, T' is a minimum spanning tree. Compare its weight to that of T: weight(7) weight(T) + w(e)-w(e') Both e and e' cross between S and V - S, and e is specifically the lightest edge of this type. Therefore w(e) S w(e'), and weight(T')