85 votes 85 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 35.8k 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.
Best answer 145 votes 145 votes Many people here have not understood the question itself. Consider a complete graph of $4$ vertices. We have a total of $6$ edges of given weights but we do not have the exact graph. Many different graphs are possible each having a different structure. Consider these $2$ graphs, both of them are different. We do not know the exact structure of the graph, so what the question wants is to find the MST of all such structures and out of these tell the weight of the MST having maximum weight. The point about the MST of a graph with unique edge weights is valid for a given structure of the graph. With the same set of edge weights more than $1$ graph is possible and all of them can have different MSTs. My solution: Draw a complete graph of $4$ vertices. Sort given edges $y$ weight in increasing order. Just like Kruskal's algorithm sort the edges by weight. MST of graph with $4$ vertices and $6$ edges will have $3$ edges. Now in any case we will have to include edges with weights $1$ and $2$ as they are minimum and Kruskal's algorithm includes minimum weight edge if it does not form a cycle. We can not have a cycle with $2$ edges. In Kruskals algorithm, an edge will be rejected if it forms a cycle with the edges already selected. To increase the weight of our MST we will try to reject the edge with weight $3.$ This can be done by forming a cycle. The graph in pic1 shows this case. This implies, the total weight of this graph will be $1+2+4 = 7.$ air1 answered Nov 8, 2016 • edited Jun 19, 2021 by Lakshman Bhaiya air1 comment Share Follow See all 16 Comments See all 16 16 Comments reply Show 13 previous comments Pranavpurkar commented Jan 16, 2022 reply Follow Share ASNR1010 +1 0 votes 0 votes shikhar500 commented Dec 4, 2022 reply Follow Share @Arjun sir images are not visible which he is referring to… plz update this ans with an image 0 votes 0 votes Akash 15 commented Jan 5 reply Follow Share where is image ? :| @Lakshman Bhaiya the ans need an update the image is missing !! 1 votes 1 votes Please log in or register to add a comment.
79 votes 79 votes Graph $G$ can be like this: shaiklam09 answered Feb 13, 2016 • edited Nov 16, 2017 by kenzou shaiklam09 comment Share Follow See all 17 Comments See all 17 17 Comments reply Show 14 previous comments Vikas123 commented Dec 14, 2018 reply Follow Share What we do if edges weight are 1,2,3,4,5,6,7,8,9 and 10. than find maximum possible weight that a minimum weight spanning tree of G have..??? 0 votes 0 votes Satbir commented Jan 24, 2019 reply Follow Share @Vikas123 then we have to include minimum 4 edges to make a spanning tree and we put edges 1 ,2 and 3 in a cycle. so 3 will be rejected. => 1 + 2 + 4 + 5 = 12 0 votes 0 votes shashank023 commented Dec 16, 2020 reply Follow Share @Satbir we can have edges 1 and 2, edge 3 makes cycle with 1-2, so take edge 4. Now edge 5 makes cycle with 1-4 and similarly edge 6 makes cycle with 2-4, so now we can only take edge 7. max MST weight= 1+2+4+7=14. 1 votes 1 votes Please log in or register to add a comment.
30 votes 30 votes ans is 7. it is said maximum weight pssbl. draw a triangle. 3 sides weight 1 2 3. and 4th point is in center. join it with tringle vertices.. got more 3 sides. new side weight 4 5 6. now draw mst. take 1 take 2. cant take 3, so take 4. 1+2+4=7 Debasmita Bhoumik answered Feb 12, 2016 • edited Feb 12, 2016 by Debasmita Bhoumik Debasmita Bhoumik comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Puja Mishra commented Jan 10, 2018 reply Follow Share U should hav drawn the image of ur answer ... 1 votes 1 votes Sunny Mukherjee commented Jan 29, 2018 reply Follow Share explain why...dont only state 0 votes 0 votes Mostafize Mondal commented Sep 5, 2018 reply Follow Share @puja.See this... 0 votes 0 votes Please log in or register to add a comment.
18 votes 18 votes Corrections or suggestions are welcomed. tanaya answered Nov 3, 2016 tanaya comment Share Follow See all 5 Comments See all 5 5 Comments reply Rajesh Pradhan commented Nov 16, 2016 reply Follow Share Nice ans. ( Actually While I was writing the ans ; I found that U already written the same what i supposed to write.Thanks anyway) 1 votes 1 votes shweta1920 commented Jul 19, 2017 reply Follow Share how ??? by applying SOME STRATEGY? chose 2,3????? 0 votes 0 votes learner_geek commented Dec 28, 2017 reply Follow Share as in 2,3 (we need to select smaller one so 2 has been selected) NOTE:-just take all possible maximum and out of all possible maximum pick minimum 0 votes 0 votes Sunny Mukherjee commented Jan 29, 2018 reply Follow Share @tanaya.... perfect one..thanks... finally it is clear 0 votes 0 votes Amit puri commented Dec 13, 2018 reply Follow Share The best answer for this question 0 votes 0 votes Please log in or register to add a comment.