Statement

Tree properties

It is useful to remind ourselves of some tree properties:

1. Tree on $n$ vertices has $n-1$ edges.
2. In a tree, there is exactly one path between every pair of vertices.
3. Any connected $G = (V,E)$ with $\vert E \vert = \vert V \vert - 1$ is a tree.

These are all proved by the equivalent tree definitions.

Greed is good … in this case

The greedy approach of just starting with an empty graph and keep adding valid edges of minimum weight, solves the MST problem.

The only problem is keeping track of the edges that are valid to include.

Kruskal’s Algorithm

Pseudocode

Run time

Correctness

So the only think left to prove Kruskal’s algorithm is correct is the proof of the cut property.

Cut property

Prim’s algorithm

Algorithm

Correctness