The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes

Let $G$ be an undirected connected graph with distinct edge weights. Let $e_{max}$ be the edge with maximum weight and $e_{min}$ the edge with minimum weight. Which of the following statements is false?

  1. Every minimum spanning tree of $G$ must contain $e_{min}$
  2. If $e_{max}$ is in a minimum spanning tree, then its removal must disconnect $G$
  3. No minimum spanning tree contains $e_{max}$
  4. $G$ has a unique minimum spanning tree
asked in Algorithms by Veteran (59.5k points)
edited by | 2.7k views
Any example in support of c?

3 Answers

+21 votes
Best answer

C the case should be written as "may or may not", to be true.

D will always be true as per the question saying that the graph has distinct weights.

answered by Boss (19.7k points)
edited by
if there is a bridge in the graph, that must be included in MST
If in a graph there is an edge which connects a pendant vertex to the graph, then however heavy that edge may be, that edge will always be included in all MST of the graph G.

So, option (c) is wrong.
+9 votes

option a is true. emin should be there in all MST

option b is true - if emax there that means that is the only edge reachable to one of the incident vertices of it. Otherwise we will select lesser weight edge incident on that vertex, Hence its removal will disconnect G

we cannot infer whether c  and d are true always. sometimes they can be false

answered by Boss (11.5k points)
(d) is actually true. Since, edge weights are unique, minimum spanning tree can be only one.
you are right

actually i missed out the point distinct edge

hence option c is the answer to the question since from the given data we cannot infer that
Even if the edge weights are unique, Can't it have multiple spanning trees? Like if ST1 contains two edges with weights 4 and 3, and ST2 contains the same edges as ST1 but instead of those two edges it contains edges with weights 2 and 5 (both pairs summing up to 7). Both will have the same total edge weight sum.

I am not sure about this, is there anything wrong in my approach?

sir it is not always true that we get unique spanning tree

its counter example is in above image

here possible mst is 5+8+10=23

and 6+7+20=23


but in the given graph minimum spanning tree cost is not 23.

minimum spanning tree is 5+6+7 = 18

What you are commented is about there are two different spanning tree of same cost.

but they are not minimum spanning tree. MInimum spanning tree is a spanning tree with minimum cost.

Please note that option D is G has a unique minimum spanning tree

0 votes

Only option C is False.

answered by (93 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,111 questions
44,694 answers
43,753 users