edited by
35,081 views
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 __________
edited by

18 Answers

3 votes
3 votes

THE ANSWER FOR THIS QUESTION IS  6 !!

sorry for the disappointment!!

now the minimum spanning tree for a graph with distinct edge weights is UNIQUE if u want reference  ( https://en.wikipedia.org/wiki/Minimum_spanning_tree)

now the given graph is having distinct edge weights so minimum spanning tree will be unique and its always 6

the question about maximum ???

there is no concept of max or min in minimum spanning tree !!!

3 votes
3 votes
Given graph will be having 6 or 7 as the weight of its MST.
We will get weight 6 when there will be no cycle formation during picking of edges weight 1,2,3 and thus 1+2+3 = 6.
But in the worst case, we will be having cycle formation when we pick edge having weight 3 and thus, in that case, we'll have to leave weight 3 and pick edge with weight 4 (always).So this will give weight 1+2+4 = 7.
Since we are having two variants of MST having weight 6 and 7, we have to choose maximum among them.
So the answer is 7.
0 votes
0 votes
This question deals with orientation of complete graph

Now we have 2 options

1) we place edges  having wt 1, 2 at digonals

2) or on sides

Because any way those edges are part of spanning tree

Iin the first case it is not possible to construct a mst neglecting edge with wt 3

But in second case we can make mst with neglecting 3 by placing such that it forms cyle
Answer:

Related questions

61 votes
61 votes
5 answers
3
Sandeep Singh asked Feb 12, 2016
28,245 views
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.