What is the maximum possible weight that a minimum weight spanning tree of G can have ?

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 __________

2Comments
Sumit Verma @sumitkgp
19 Jul 2017 10:13 pm
shivani @shivani1234
21 Jul 2017 01:58 pm

if we place 3 on diagonal it will form a cycle so it is not taken , else if it is placed somewhere else then MST=1+2+3=6

  • if we place 3 on diagonal it will form a cycle and 4 on another diagonal or on other edges such that it doesn't form a cycle then MST=1+2+4=7
  • so, max MST=7.