Skip to content
GATEiit

GATE CSE 2022 Q49: MST facts for a graph with distinct edge weights

Question

Consider a simple undirected weighted graph GG, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of GG is/are TRUE?

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: A, B, C (official GATE 2022 final answer key)

Concept used: Cut property and Kruskal's algorithm; distinct weights make the MST unique.

First step: Run Kruskal mentally: the two lightest edges can never form a cycle, and in a simple graph three edges form a cycle only as a triangle.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2022 questions →