Consider a connected undirected graph G=(V,E) in which every edge e∈E has a distinct and nonnegative cost. Let T be an MST and P a shortest path from some vertex s to some other vertex t. Now suppose the cost of every edge e of G is increased by 1 and becomes ce+1. Call this new graph G′. Which of the following is true about G′ ? a) T must be an MST and P must be a shortest s - t path. b) T must be an MST but P may not be a shortest s - t path. c) T may not be an MST but P must be a shortest s - t path. d) T may not be an MST and P may not be a shortest s−t path. Pls use Kruskal's algorithm to reason about the MST.

Consider a connected undirected graph G=(V,E) in which every edge e∈E has a distinct and nonnegative cost. Let T be an MST and P a shortest path from some vertex s to some other vertex t. Now suppose the cost of every edge e of G is increased by 1 and becomes ce+1. Call this new graph G′. Which of the following is true about G′ ? a) T must be an MST and P must be a shortest s - t path. b) T must be an MST but P may not be a shortest s - t path. c) T may not be an MST but P must be a shortest s - t path. d) T may not be an MST and P may not be a shortest s−t path. Pls use Kruskal's algorithm to reason about the MST.