GATE CS 2024 Set 2 Q49 — 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?

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}?$

Let $\textit{G(V,E)}$ be a directed graph, where $\textit{V} = \{ 1, 2, 3, 4, 5 \}$ is the set of vertices and $\textit{E}$ is the set of directed edges, as defined by the following adjacency matrix $\textit{A}.$ $$A [i][j] = \left\{\begin{matrix} 1, & 1 \leq j \leq i \leq 5 \\ 0, & \text{otherwise}\end{matrix}\right.$$ $A[i][j] = 1$ …