Other answer is incorrect

Problem 1. (15 points) Consider an undirected connected graph G = (V, E) with edge costs ce > 0 for e E which are all distinct. (a) [8 points). Let E' CE be defined as the following set of edges: for each node v, E' contains the cheapest of all edges incident on v, i.e., the cheapest edge that has v as one of its endpoints. Is the graph (V, E') connected? Is it acyclic? For both questions, provide a proof or a counter-example with explanations. (b) (7 points). Consider the following outline for an algorithm, which starts with an empty set T of edges: Let E' contain the cheapest edge out of each connected component of (V,T). Add E' to T, and repeat until (VT) is connected. Show that this algorithm outputs a minimum spanning tree of , and can be implemented in time 0(m logn). Hints: Each iteration of this algorithm can be viewed as applying the operation from part (a) on a contracted graph, where each connected component of (V,T) corresponds to a node. If you want, you are welcome to use the efficient implementation of the Union-Find data structure which supports Find and Union in logarithmic time, as described in Chapter 4.6 of the KT book. However, this implementation is not necessary, and focusing on it may mislead you from the basic idea. We recommend thinking about how many iterations it will take until (V,T) is connected