1. Let G = (V, E) be a connected graph and c: ER be a cost...

Transcribed Image Text:

1. Let G = (V, E) be a connected graph and c: ER be a cost function on its edges. True or false? (Justify your answers!) (a) Any edge of minimum cost in G is contained in a certain minimum cost spanning tree (MST) of G. (b) If G has a cycle, C, whose minimum cost edge is unique on C, then that edge must be contained in every MST of G. (c) If an edge is contained in a certain MST of G, then that edge must be of minimum cost in a certain cut of G. 1. Let G = (V, E) be a connected graph and c: ER be a cost function on its edges. True or false? (Justify your answers!) (a) Any edge of minimum cost in G is contained in a certain minimum cost spanning tree (MST) of G. (b) If G has a cycle, C, whose minimum cost edge is unique on C, then that edge must be contained in every MST of G. (c) If an edge is contained in a certain MST of G, then that edge must be of minimum cost in a certain cut of G.