Consider the following variant of the minimum spanning tree problem, how do I do task 1 and 2? In addition, for task 2 what kind of proving skills (such as induction or proof by contradiction) need to be applied and how?

Description Consider the following variant of the MST problem. We are given an undirected, complete graph G (V,E) with n vertices and m() edges, a positive (not necessarily unique) edge cost ce for each edge in E. We are also given a subset of vertices ASV. The goal is to find a minimum cost set of edges FCE such that (V,F) is connected, and degp(u)1 for each u E A (i.e. every u E A has degree 1 in the graph (V,F)) Task 1 [20 marks] Show that simply computing the MST does not work. In particular, show that there is a graphG-(V, E) with edge costs ce and a subset of vertices AV such that the minimum spanning tree X for this graph has degr(u) > 1 for some u A. Your task is to give such a graph on three vertices z, y, z. You need to specify: 1. the edge weights c(C( 2. the subset ACV, 3. a minimum spanning tree F, and 4. a vertex u A such that degr(u) > 1 Task 2: [20 marks] We will now develop some insight into the structure of the optimal solution. Consider an optimal solution F and let FA CF be the set of edges in X incident to vertices in A. Prove that (V\A, F\FA) is connected graph and moreover, is a minimum spanning tree of the complete subgraph of G on the vertices V \ A Description Consider the following variant of the MST problem. We are given an undirected, complete graph G (V,E) with n vertices and m() edges, a positive (not necessarily unique) edge cost ce for each edge in E. We are also given a subset of vertices ASV. The goal is to find a minimum cost set of edges FCE such that (V,F) is connected, and degp(u)1 for each u E A (i.e. every u E A has degree 1 in the graph (V,F)) Task 1 [20 marks] Show that simply computing the MST does not work. In particular, show that there is a graphG-(V, E) with edge costs ce and a subset of vertices AV such that the minimum spanning tree X for this graph has degr(u) > 1 for some u A. Your task is to give such a graph on three vertices z, y, z. You need to specify: 1. the edge weights c(C( 2. the subset ACV, 3. a minimum spanning tree F, and 4. a vertex u A such that degr(u) > 1 Task 2: [20 marks] We will now develop some insight into the structure of the optimal solution. Consider an optimal solution F and let FA CF be the set of edges in X incident to vertices in A. Prove that (V\A, F\FA) is connected graph and moreover, is a minimum spanning tree of the complete subgraph of G on the vertices V \ A