Let G be a weighted connected undirected graph with distinct positive edge…

Key idea: adding the same constant to every edge preserves comparisons of spanning-tree weights and the order of individual edge weights, but it does not preserve shortest paths in general.

• Why statement P (Minimum spanning tree of G does not change) is true: For a graph with n vertices, any spanning tree has exactly n−1 edges. If you add a constant c to every edge, the total weight of any spanning tree increases by c*(n−1). Since this same amount is added to every spanning tree, the spanning tree that minimized the original total weight still minimizes the new total weight. Equivalently, the ordering of edge weights is unchanged, so Kruskal's or Prim's algorithm will select the same edges.

• Why statement Q (Shortest path between any pair of vertices does not change) can be false: Different s–t paths can have different numbers of edges, so adding c to each edge increases the total path cost by c times the number of edges on that path. This can change which path is cheapest.

Conclusion: Statement P is true and statement Q is not guaranteed, so the correct answer is that only the statement about the minimum spanning tree staying the same holds.