Let G = (V, E) be an undirected connected graph and let c : E R + be a function specifying the costs of the edges, i.e., every edge has a positive cost. Assume that no two edges have the same cost. Given a set S V , where S contains at least one element and is not equal to V , let eS denote the edge in E defined by applying the cut property to S, i.e., eS = arg minecut(S) ce.

In this definition, the function arg min is just like min but returns the argument (in this case the edge) that achieves the minimum. Let F be set of all such edges, i.e., F = {eS, S V, S 6= }. In the definition of F, S ranges over all subsets of V other than the empty set and V itself. Answer the following questions, providing proofs for all questions.

1. Consider the graph induced by the set of edges in F, i.e., the graph G0 = (V, F). Is G0 connected?

2. Does G0 contain a cycle?

3. How many edges does F contain?

4. What conclusion can you draw from your answers to the previous statements?

Edit: I'm guessing that the conclusion is that G0 is a minimal spanning tree and we have to prove that it's connected, doesn't have a cycle, and has n - 1 edges?