1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

# Let G be an undirected connected graph with distinct edge weights. Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false?

A
G has a unique minimum spanning tree
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
B
No minimum spanning tree contains emax
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
C
If emax is in a minimum spanning tree, then its removal must disconnect G
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
D
Every minimum spanning tree of G must contain emin
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
Open in App
Solution

## The correct option is B No minimum spanning tree contains emax(a) All the edge weights are distinct, so every minimum spanning tree of G must contain emin (kruskal's algorithm will pick emin first) (b) If emax is in a minimum spanning tree, then surely its removal must disconnect G (i.e. emax must be a cut edge). (c) A minimum spanning tree can contain emax if its removal disconnect G (i.e. it s a cut edge). So this option is false. For example, in the graph given below, the edge cd is a maximum weight edge but still is present in the minimum spanning tree. (d) Since all edge weights are distinct G has a unique minimum spanning tree.

Suggest Corrections
1
Join BYJU'S Learning Program
Related Videos
Permutation
QUANTITATIVE APTITUDE
Watch in App
Explore more
Join BYJU'S Learning Program