*(Guest post by Long Nguyen)*

November 6^{th} lecture centered around the optimality of Kruskal’s algorithm and Prim’s Algorithms. We spend most of the time proving the Lemma (Assume all the edge cost are distinct. Let , and is the min cost edges ( and ), then is in all MST).

We talked about **Optimality of Kruskal’s Algorithm**. We assume is not empty, is not empty, and is the first crossing edge considered. The Kruskal’s Algorithms produces no cycle by designed and we just need to show that is connected. *( is defined to be the set of nodes connected to one end-point of $e$.–Atri)*

We talked about **Optimality of Prim’s Algorithm**. is defined for us. By induction, we show that is a tree.

We then proceeded to prove the Lemma.

*Proof idea:* Contradiction and an exchange argument. For contradiction we assume (MST) doesn’t have . ( is min cost crossing edge).

*Rest of the proof:* Show that exist st. contains . is a spanning tree and which is a contradiction as is MST.

*Existence of :*

is connected implies a crossing (edge we’re after.)

- ( is cheapest crossing edge and edge weights are distinct).
- so .

This neglect fact that and is connected in . *[To be more precise, we need to show that is connected*. *–Atri]* If it is not removing from and replacing it with causes to become disconnected. So we must make sure that removing and adding does not disconnect . Also if has a cycle if does.

We ended lecture there.

## Leave a Reply