Consider an undirected graph G (V, E) with non-negative edge weights. G is defined over set of vertices V and edge set E, where e(u, v, k) ε E denotes a weighted edge between vertices and v(u, v ε V) with weight k.

1. Which of the following is/are true regarding graph G:

a. There may not exist any MST for G.

b. There will always exist a MST for G.

c. Assume two MST T1 and T2 for G. Then T1 = T2

d. Assume two MST T1 and T2 for G. Then (wT1) = (wT2). (w (T) denotes the sum of weights of all edges in T).

e. BFS of G returns a spanning tree.

Answer:b. There will always exist a MST for G.d. Assume two MST T1 and T2 for G. Then (wT1) = (wT2). (w (T) denotes the sum of weights of all edges in T).