PLEASE do not just copy/paste the answer for this question which is already provided on here by someone else, that answer is insufficient.

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 but the first question.

Problem 1 (30 points) 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 CV, 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 mineEcut(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 CV, S # 0}. 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 but the first question. (i) (5 points) How many distinct cuts does G have? We will use the same definition as in class: a cut is a set of edges whose removal disconnects G into two or more non-empty connected components. Two cuts are distinct if they do not contain exactly the same set of edges. For this question, just provide an upper bound. (ii) (8 points) Consider the graph induced by the set of edges in F, i.e., the graph G' = (V, F). Is G' connected? (iii) (7 points) Does G' contain a cycle? (iv) (5 points) How many edges does F contain? (v) (5 points) What conclusion can you draw from your answers to the previous statements