## Problem2D

Problem2D: Here is a variation on the above greedy algorithm. Let ${ x_{1}}$ be any vertex of a weighted connected graph ${G}$ with ${n}$ vertices and let ${T_{1}}$ be the subgraph with the one vertex ${x_{1}}$ and no edges. After a tree (subgraph) ${ T_{k}}$, ${k, has been defined, let ${e_{k}}$ be a cheapest edge among all edges with one end in ${V(T_{k})}$ and the other end not in ${V(T_{k})}$, and let ${T_{k+1}}$ be the tree obtained by adding that edge and its other end to ${T_{k}}$. Prove that ${T_{n}}$ is a cheapest spanning tree in ${G}$.

Solution: This algorithm is called Prim’s algorithm. The proof can be found in Wikipedia. We state the proof here again. Suppose ${T^{\prime }}$ is a cheapest spanning tree. If ${T_{n}=T^{\prime }}$, the proof finished. Otherwise, let ${e_{k}}$ be the first edge not in ${T^{\prime }}$ when we generate ${T.}$ Denote by ${V}$ all the edges before we add ${e_{k}}$. Since ${ T^{\prime }}$ is a spanning tree, there is a unique cycle in ${T^{\prime }}$ containing two ends of ${e_{k}}$. We claim that there is at least one edge ${w}$ having one end in ${V}$, and the other end not in ${V}$. Otherwise, if all the vertices of the cycle are in ${V}$, ${T_{n}}$ will contain a cycle, a contradiction. On the other hand, not all the vertices are outside of ${V}$ since one end of ${e_{k}}$ is in ${V}$. So there must exists at least one edge ${w }$ having one end in ${V}$ and the other not in ${V}$. By Prim’s algorithm, ${ c(w)\geq c(e_{k})}$, otherwise ${w}$ would be chosen rather than ${e_{k}}$. Add ${ e_{k}}$ to ${T^{\prime }}$ and delete ${w}$, we obtain a new spanning tree ${ T^{\prime \prime }}$ which is still a cheapest spanning tree. Keep doing this until we obtain a cheapest spanning tree identical to ${T}$,

Note: The hint in the book says that ${T_{n}}$ has the property that for every edge ${e}$ in ${T_{n}}$, the ends of ${e}$ are in different components of ${G:\left\{ w:c(w). And any spanning having this property will be a cheapest spanning tree. I still do not know how to show the second part. I shall be happy if anyone can suggest the solution.