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.