Question Details

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?

Options

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

Show Answer
Correct Answer
A In every cycle C of G, the edge with the largest weight in C is not in any MST
D For every vertex v ∈ V, the edge with the smallest weight incident on v is in every MST

Solution :

The correct statements are:
1. In every cycle C of G, the edge with the largest weight in C is not in any MST
2. For every vertex v ∈ V, the edge with the smallest weight incident on v is in every MST

Here is the detailed step-by-step explanation of why these statements are correct:

1. Explanation of the Cycle Property Statement:

Let C be any cycle in the graph G, and let e be the edge in C with the strictly largest weight (since edge weights are unique). We want to prove that e cannot belong to any minimum spanning tree (MST) of G.

Suppose, for the sake of contradiction, that there is an MST T that contains the edge e. If we delete the edge e from T, the tree T is disconnected into exactly two components, say V1 and V2.

Since e is part of the cycle C, there must exist at least one other edge e′ in the cycle C that also connects V1 and V2. Since e is the unique edge with the largest weight in cycle C, the weight of e′ must be strictly less than the weight of e:

weight(e′)<weight(e)

If we construct a new spanning tree T′ by removing e and adding e′, the new tree T′=T-{e}∪{e′} remains connected and spans all vertices. However, the total weight of T′ is strictly less than the total weight of T. This contradicts the assumption that T is a minimum spanning tree. Thus, the edge with the largest weight in any cycle C cannot be in any MST.

2. Explanation of the Cut Property (Incident Edges) Statement:

For any vertex v∈V, let us define a cut in the graph that separates v from all other vertices. This cut is represented by the partition ({v},V\{v}).

The edges crossing this cut are precisely all the edges incident on the vertex v. By the Cut Property of minimum spanning trees, for any cut of a graph, the edge with the minimum weight crossing that cut must belong to the MST. Because all edge weights in the graph G are unique, there is a unique edge emin incident on v that has the smallest weight among all incident edges.

Since emin is the unique minimum-weight crossing edge for the cut ({v},V\{v}), it must be included in every MST of G.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: