TIFR CSE 2021 | Part B | Question: 10

Question

Let $G$ be a connected bipartite simple graph (i.e., no parallel edges) with distinct edge weights. Which of the following statements on $\text{MST}$ (minimum spanning tree) need $\text{NOT}$ be true?

• A. $G$ has a unique $\text{MST}$.
• B. Every $\text{MST}$ in $G$ contains the lightest edge.
• C. Every $\text{MST}$ in $G$ contains the second lightest edge.
• D. Every $\text{MST}$ in $G$ contains the third lightest edge.
• E. No $\text{MST}$ in $G$ contains the heaviest edge.

Answer 1

Option E is not necessarily True.

Example: edge $a-c$ is heaviest, but will be present in every MST of this bipartite graph.

It’s a simple connected graph and edge weights are given distinct, therefore we’ll have a unique MST for every such graph.

Comments

if a Graph is simple connected bipartite graph then definitely MST of G contains the heaviest edge.so, statement E is directly false even not a may be may not be case.