Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum spanning tree whose weight is the smallest among all spanning trees that are not minimum spanning trees in $G$.
Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)
I think Algorithms tag should be added in this question.
To see that the second-best minimum spanning tree need not be unique, here is a weighted, undirected graph with a $unique\ MST$ of weight 7 and $two\ second-best\ MST's$ of weight 8:
In the graph we have all edge weights are distinct so we will get unique minimum and maximum spanning tree.
Each Cycle must exclude maximum weight edge in minimum spanning tree.
Here, we have two cycle of $3$ edges, $a-d-e$ and $c-g-k.$
For second best minimum spanning tree, exclude $a-e$ edge and include $d-e$ edge
Other way for second best minimum spanning tree: exclude $c-g$ edge and include $g-k$ edge.
So, e should be the answer.
And we can have more than one second best minimum spanning tree because different combinations of edge may give second largest value.
Can u give some examples
the second minimum spanning tree wil contain the value +1 of the minimum spanning tree choosen