2 votes 2 votes 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? $G$ has a unique $\text{MST}$. Every $\text{MST}$ in $G$ contains the lightest edge. Every $\text{MST}$ in $G$ contains the second lightest edge. Every $\text{MST}$ in $G$ contains the third lightest edge. No $\text{MST}$ in $G$ contains the heaviest edge. Algorithms tifr2021 algorithms minimum-spanning-tree + – soujanyareddy13 asked Mar 25, 2021 • recategorized Nov 20, 2022 by Lakshman Bhaiya soujanyareddy13 735 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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. Nikhil_dhama answered Apr 4, 2021 • edited Nov 20, 2022 by gatecse Nikhil_dhama comment Share Follow See 1 comment See all 1 1 comment reply geeks_god commented Sep 21, 2023 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.