Computer Sciences > Gate 2016 Set-1 > Graph Theory
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
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
Explanation
Correct : Graph Theory
Similar Questions
What is the worst-case time complexity of insertion in an AVL tree?
Which operations on a binary search tree have O(h) complexity?
Compare search complexities of sorted array vs balanced BST.