# Prims algorithm

### Overarching idea

Build a subgraph by repeatedly choosing the minimum edge connecting the subgraph to another vertice.

### Steps

1. Choose a vertex as the initial MST subgraph, S.

2. Choose the minimum edge which connects S to any other vertex in the graph, G. This vertex should not be connected to S.

3. Repeat step 2.

### Proof of correctness

Assume Prim’s algorithm does not given an MST.

Let M be a MST for a weighted graph G = (V, E).

We know PRIM constructs a sequence of trees $$T_{i}$$, where $$T_{i}$$ contains i vertices and i-1 edges.

Let $$T_{k+1}$$ be the first tree that has an edge not contained in the MST.

Using the cut property to $$T_{k}$$ and $$V - T_{k}$$:

• The min cost edge from $$T_{k}$$ to $$V - T_{k}$$ must be in min spanning tree

• Prim’s algorithm chooses that edge by definition

• Hence $$T_{k+1}$$ must have the same edges as the MST.