edited by
15,411 views
38 votes
38 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
edited by

5 Answers

Best answer
36 votes
36 votes

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.

Correct Answer: $C$

edited by
16 votes
16 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

6 votes
6 votes
Option 1 :- Every minimum spanning tree of G must contain $e_{min}$.

Kruskal's algorithm always picks the edges in ascending order of their weights while constructing a MST of G. So yes , it is true.

 

Option 2 : -  If $e_{max}$ is in a minimum spanning tree, then its removal must disconnect G .

$e_{max}$ would be included in MST if and only if , $e_{max}$ is a bridge between two connected components , removal of which will surely disconnect the graph.

Option 3 :- No minimum spanning tree contains $e_{max}$.

Contradictory statement , already proved in option 2 that $e_{max}$ can be in MST. Thus option 3 is false.

Option 4 :- $G$ has a unique minimum spanning tree.

G has unique edge weights , so MST will be unique . In case if edge weights were repeating , there could've been a possibility of non-unique MSTs.

Thus it is true.
3 votes
3 votes

Only option C is False.

Answer:

Related questions

79 votes
79 votes
10 answers
2
Kathleen asked Sep 14, 2014
22,587 views
Consider the following functions$f(n) = 3n^{\sqrt{n}}$$g(n) = 2^{\sqrt{n}{\log_{2}n}}$$h(n) = n!$Which of the following is true?$h(n)$ is $O(f(n))$$h(n)$ is $O(g(n))$$g(n...