edited by
2,724 views
15 votes
15 votes

Let $G$ be a connected simple graph (no self-loops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of the edges in decreasing order of weight. Which of the following statements is FALSE?

  1. The edge $e_{1}$ has to be present in every maximum weight spanning tree.
  2. Both $e_{1}$ and $e_{2}$ have to be present in every maximum weight spanning tree.
  3. The edge $e_{m}$ has to be present in every minimum weight spanning tree.
  4. The edge $e_{m}$ is never present in any maximum weight spanning tree.
  5. $G$ has a unique maximum weight spanning tree.
edited by

3 Answers

Best answer
17 votes
17 votes

a) & c) are trivially true. Edge with max value $e_1$ must be present in Maximum spanning tree & same with minimum.

e) This is true, because all edge weights are distinct. maximum spanning tree is unique.

b) $e_1$ & $e_2$ must be present in Maximum spanning tree. I'll prove it using Kruskal Algorithm.

We will first insert weight with biggest value, $e_1$. Then we insert $e_2$ (second highest) . $2$ edges do not create cycle. Then we can go on from there inserting edges according to edge weights. As they have just asked for top $2$ edges, using Kruskal Algo we can say that top $2$ edges must be in Maximum spanning tree.

d) This is false. There are chances that this $e_m$ weight edge is cut edge(Bridge) Then it must be inserted to from any spanning tree.

D is answer.

We can not say the same for Top $3$ as they can create cycle & They we can not take $a_3$ to make spanning tree.

Kruskal Algo Reference: http://stackoverflow.com/questions/4992664/how-to-find-maximum-spanning-tree

edited by
3 votes
3 votes

Option D) The edge em is never present in any maximum weight spanning tree
                 

                 let the ebe the pendant edge then it has to be in max spanning tree.

0 votes
0 votes

In case of distinct edges, an MST will ALWAYS have the lightest, and the second lightest edge. Complement the circumstances here, and Options A and B become True. Option C is also True

Note that the third lightest edge may or may not be included in the MST, because it might form a loop.


Whenever we have distinct edges, we ALWAYS get a unique MST. Complement the circumstances, and Option E becomes True.


In an MST, the only reason we include a heavier edge, when we have lighter options is when that edge is a bridge (cut edge). We need to include it in order to keep the MST connected.

For similar reason, in a Maximum-Spanning-Tree, if the minimum-weight edge is a bridge, we will include it.

Option D is False, and is our answer.

 

https://gateoverflow.in/39727/gate2016-1-40

Answer:

Related questions