GATE CS 2014 Set 2 Q52 — Minimum Spanning Trees

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_{1}(u, v)$ and $d_{2}(u, v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$, respectively. Which ONE of the options is CORRECT for all possible $G, T, u$ and $v$ ?

The maximum value of $\text{x}$ such that the edge between the nodes $\text{B}$ and $\text{C}$ is included in every minimum spanning tree of the given graph is _________. (answer in integer)

​​​​Let $\text{G}$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in $\text{G}$ before and after the edge weight update?

The number of distinct minimum-weight spanning trees of the following graph is

Consider a simple undirected weighted graph $\textit{G},$ all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $\textit{G}$ is/are $\text{TRUE}?$