11. (a) Consider a weighted graph G, where all weight values are different. Imagine that each vertex v, from among the edges touching v it chooses the one with minimum weight as its "favorite" edge. Prove that some edge in G will be chosen as favorite by both its endpoints. (b) Consider a weighted graph G, where all weight values are different, and let T be a minimum spanning tree of G. Prove that for each vertex v, the edge touching v that has minimum weight must be in T. 12. Consider the problem of computing single-source shortest paths on a graph where all weights values are either 1 or 2 . Give an algorithm for this problem that works in time O(m+n). 11. (a) Consider a weighted graph G, where all weight values are different. Imagine that each vertex v, from among the edges touching v it chooses the one with minimum weight as its "favorite" edge. Prove that some edge in G will be chosen as favorite by both its endpoints. (b) Consider a weighted graph G, where all weight values are different, and let T be a minimum spanning tree of G. Prove that for each vertex v, the edge touching v that has minimum weight must be in T. 12. Consider the problem of computing single-source shortest paths on a graph where all weights values are either 1 or 2 . Give an algorithm for this problem that works in time O(m+n)