Computer Sciences > GATE 2026 SET-1 > Graph Algorithms
Let G(V, E) be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning trees (MST) of G is/are true?
A
In every cycle C of G, the edge with the largest weight in C is not in any MST
B
In every cycle C of G, the edge with the smallest weight in C is in every MST
C
For every vertex v ∈ V, the edge with the largest weight incident on v is not in any MST
D
For every vertex v ∈ V, the edge with the smallest weight incident on v is in every MST

Correct : a,b,d

Similar Questions

Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v in V. Let...
#1386 MCQ
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a is added to the weight of every edge. Which ONE of the foll...
#1445 MCQ
Consider the following algorithm someAlgo that takes an undirected graph G as input. The output of someAlgo (T) for the tree shown in the given figure is _____...
#1466 NAT

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: