Looking for some help with starting points more so than solutions here. How can I go about proving 1, 2, and 3? I don't understand exactly what $\displaystyle S$ is? Just an array of all $\displaystyle e_{v}$ basically? Additionally I don't understand $\displaystyle G$ vs. $\displaystyle G_{S}$?

Design and analyze a minimum spanning tree recursive algorithm that only uses the adjacency list representation of the graph and no other data structures. Assume that edge costs are distinct.

- For each vertex $\displaystyle v$, let $\displaystyle e_{v}$ be the minimum-cost edge adjacent to $\displaystyle v$. Let $\displaystyle S$ be the union of all such edges. Prove that $\displaystyle S$ is acyclic.
- Show that you can find $\displaystyle S$ in $\displaystyle O(m)$ time, where $\displaystyle m$ is the number of edges in the graph.
- We contract an edge $\displaystyle e = u - v$ by creating a new vertex $\displaystyle x$, connecting $\displaystyle x$ to all of $\displaystyle u$’s neighbours and all of $\displaystyle v$’s neighbours and deleting $\displaystyle u$ and $\displaystyle v$ and all the edges adjacent to $\displaystyle u$ and $\displaystyle v$. Let $\displaystyle G_{S}$ be the graph obtained by contracting all the edges in $\displaystyle S$. Show that one can build $\displaystyle G_{S}$ from $\displaystyle G$ and $\displaystyle S$ in $\displaystyle O(m)$ time.
- Show that the number of vertices in $\displaystyle G_{S}$ is at most one half of the number of vertices in $\displaystyle G$.
- Use the above ideas to give pseudocode for a recursive algorithm to find a minimum spanning tree. The algorithm should take as input a graph with edge costs and return the set of edges forming the minimum spanning tree.
- Give a recurrence relation for the running time of this algorithm. Solve the recurrence relation.