GATE | GATE-CS-2016 (Set 1) | Question 49

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is.

[This Question was originally a Fill-in-the-Blanks question] (A) 6
(B) 7
(C) 8
(D) 9

Answer: (B)

Explanation: One graph that has maximum possible weight of spanning tree

Leave a Reply

Your email address will not be published. Required fields are marked *