\(G = (V,E)\) is an undirected simple graph in which each edge has a distinct…

GATE · 2016 · CS · Set 1 · Computer Science & IT

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

I. If e is the lightest edge of some cycle in GG, then every MST of G includes ee

II. If e is the heaviest edge of some cycle in GG, then every MST of G excludes ee

  1. A.

    I only

  2. B.

    II only

  3. C.

    both I and II

  4. D.

    neither I nor II

Attempted by 277 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…