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.

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