# Prims algorithm

### Overarching idea

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

### Steps

Choose a vertex as the initial MST subgraph, S.

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

Repeat step 2.

### Proof of correctness

#### Proof by contradiction

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.