GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes

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
asked in Graph search, minimum spanning trees, shortest paths by gate

1 Answer

0 votes
If e is the heaviest edge of some cycle in G, then every MST of G excludes e
answered by gate

Related questions

The best answer to any question