Problem 2 (30 points): This question is related to two claims made by Professor Smart, who has also stated that he is smarter than the instructor and all the students in this class. We will examine his smartness by verifying the claims that he made. Given an undirected, weighted graph G (with non-negative weights w(u, v) for each edge (u, ), and a constant D>0, Professor Smart defines the graph G+ as follows: G + D is identical to G except we add the constant D to each edge weight. (a) [15 points] Professor Smart claims that: a minimum spanning tree (MST) of G is always an MST of G (b) [15 points] Professor Smart claims that: a shortest path between vertices s andt in G is always a shortest path between s and t in G+D For each of the above two claims, your task is the following . If the claim is true, then provide a proof of the claim. This will show that Professor Smart was indeed smart. . If the claim is false, provide a counter-example and explain why the counter-example shows the claim is false. This will show that Professor Smart was not so smart after all