GATE CSE 2016 | Set 1 | Question: 40

Question

$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE?

1. If $e$ is the lightest edge of some cycle in $G$, then every MST of $G$ includes $e$.
2. If $e$ is the heaviest edge of some cycle in $G$, then every MST of $G$ excludes $e$.

• A. I only.
• B. II only.
• C. Both I and II.
• D. Neither I nor II.

Comments

Very Good Question.

---

Similar question

https://gateoverflow.in/3813/gate2005-it-52

(II) follows reverse krushal's algo http://www.geeksforgeeks.org/reverse-delete-algorithm-minimum-spanning-tree/

---

$1$ is false here because it can be possible that an edge is lightest for some cycle bt same edge can  be maximum for other cycle too As in the given best answer 3 is the lowest weight edge for cycle $3-4-5$ bt it is heaviest for $1-2-3$  .

Answer 1

I think answer is D.

Statement I is wrong.

Statement II is also wrong, consider any graph where between any two nodes there are two paths, first path consists of edges with weights 2 and 8, second path has weight 5 and 7. So, MST would include that heaviest weight in that cycle.

Comments

You are doing shortest path and not MST.

---

@Arjun Suresh sir finally i am able to see how u look like grateful to the visionary pro

Answer 2

here it is given that all edges have distinct value. so by any algo prims or kruskal we are going to add e if it is lightest edge.

So first statement is always true

and 2nd statement is also true becouse we will always exclue one with the heaviest wieght

Answer 3

if for the same question the options were given like :-

1. If e is the lightest edge  in G, then every MST of G includes e.
2. If e is the heaviest edge in G, then every MST of G excludes e.

then option 1 would have been true while option 2 would be false coz what if the edge e is a brigde then we have to take it in MST.

but as cycle is there,so 

it might be the case that for one cycle it is the lightest but for another cycle heaviest so we cant take it .