a) Let G = (V,E) be a weighted graph and let T be a minimum spanning tree of G. The path in T between any pair of vertices v_1 and v_2 must be a shortest path in G.
True or False?
b) If an edge e = (u,v) is in a minimum spanning tree of an undirected graph G = (V,e) with nonnegative weight function w, then there exist two vertices x and y in G such that e is on a shortest path from x to y.
True or False?
c) Given a bipartite graph G = (V,E) and a matching M is a set of E, it is possible to determine if M is a maximum matching in G in worst case O(E+V) time.
True or False?