# Why do the swap step in Prim's algorithm for minimum spanning trees?

I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees. Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum spanning tree of $G(V,E)$and let us call that $A$ such $A\subset B$, the edge with the least weight connecting $A$ to $V-A$ will always be in the minimum spanning tree ? The professor has done the swap step at point 59:07 seconds in the video.

• What kind of "why" are you looking for? (There are many proofs...) – Raphael Sep 19 '12 at 21:20

The proof goes by contradiction, that is you assume that the edge $(u,v)$ is not in the MST $T$. Don't be confused by the board, it has to be $(u,v)\not \in T$. Let $(a,b)$ the edge that we swap with $(u,v)$. Bot edges are cut edges between $A$ and $A\setminus V$. The tree $T'$ after the swap has weight $$w(T')=w(T)+w((u,v))-w((a,b)).$$ As a consequence $w(T')<w(T)$, which is a contradiction and therefor the assumption $(u,v)\not\in T$ was wrong.