86 votes 86 votes 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 __________ Algorithms gatecse-2016-set1 algorithms minimum-spanning-tree normal numerical-answers + – Sandeep Singh asked Feb 12, 2016 • edited Nov 16, 2017 by kenzou Sandeep Singh 36.4k views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments codeitram commented Jan 22, 2021 reply Follow Share It is not at all rocket science: Here is the solution You pick up four min edges to get MST so you pick edge with weight 1 then 2 as no choice but when picking up 3 you can ask can I avoid this one so that I can pick 4 or above which has greater weight and answer is yes you simply make weight 3 edge as so that cycle is formed, and now will have to pick edge with weight 4 as you have no choice and no additional cycle can be formed as graph is complete 4 0 votes 0 votes Adi27 commented Oct 9, 2021 reply Follow Share @arjun sir graph is complete that is all distinct vertices are connected with unique edge so only one graph structure is possible ? Square shape with diagonal vertices connected No of edges = 4*(4-1)/2 = 6 edges as given in graph 0 votes 0 votes Ray Tomlinson commented Jan 22 i edited by Ray Tomlinson Jan 22 reply Follow Share I think there are only 2 mst possible with min weight 6,7 so answer will be 7this question gets to many view just due to wrong interpretaion of question i.e. what actually asking in question is confusing means should we apply mst algo or not like this confusion . 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Answer should be 1, 2 and 4… Why? Given that its complete graph so we will have cycle for sure as soon as we add 3rd edge.. now there are many graphs possible….First draw 2 edges...which least weights(1 and 2 ) note we cannot have cycle with 2 edges but if we add 3rd we will have cycle...now add the 3rd edge such a way the next minimum which weight edge which is 3 in our case forms a cycle..next possible least weight edge would be 4...and includes all vertex.. vipin.gautam1906 answered Nov 24, 2020 vipin.gautam1906 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes The Best possible arrangement which can give minimum cost spanning tree with maximum weight is Which gives weight as 1 + 2 + 4 = 7 ProtonicRED answered Oct 26, 2021 ProtonicRED comment Share Follow See all 0 reply Please log in or register to add a comment.