## Minimum spanning tree recursive algorithm using only adjacency list

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 $S$ is? Just an array of all $e_{v}$ basically? Additionally I don't understand $G$ vs. $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.
1. For each vertex $v$, let $e_{v}$ be the minimum-cost edge adjacent to $v$. Let $S$ be the union of all such edges. Prove that $S$ is acyclic.
2. Show that you can find $S$ in $O(m)$ time, where $m$ is the number of edges in the graph.
3. We contract an edge $e = u - v$ by creating a new vertex $x$, connecting $x$ to all of $u$’s neighbours and all of $v$’s neighbours and deleting $u$ and $v$ and all the edges adjacent to $u$ and $v$. Let $G_{S}$ be the graph obtained by contracting all the edges in $S$. Show that one can build $G_{S}$ from $G$ and $S$ in $O(m)$ time.
4. Show that the number of vertices in $G_{S}$ is at most one half of the number of vertices in $G$.
5. 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.
6. Give a recurrence relation for the running time of this algorithm. Solve the recurrence relation.