edited by
20,422 views
71 votes
71 votes

Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE?

  1. There exists a cutset in $G$ having all edges of maximum weight.
  2. There exists a cycle in $G$ having all edges of maximum weight.
  3. Edge $e$ cannot be contained in a cycle.
  4. All edges in $G$ have the same weight.
edited by

9 Answers

Best answer
43 votes
43 votes

Option $A$ is correct.

Questions says the MST of graph $G$ contain an edge $e$ which is a maximum weight edge in $G$. Need to choose the answer which is always true to follow the above constraint.

Case 1:

Option B says that if edge $e$ is in MST then for sure there is a cycle having all edges of maximum weight. But it is not true always because when there is only n-1 edges( but no cycle) in graph then also maximum edge has to be taken for MST.

Case 2:

Option C says otherwise. That if e is in MST then it cannot be in any cycle that is wrong as if there is a cycle with all maximum edges then also e will be in MST

Option D says all edges should be of same weight same explanation if there are $n-1$ distinct edges( but no cycle)  in $G$ then have to take all edges including maximum weight edge.

And at last option A says if e is in MST then for sure there is a cut-set ( A subset of Edge set of G whose removal disconnects the graph) in $G$ having all edges of maximum weight. And it is true.

Because then only we maximum weight edges has to be taken in MST.

For eg. If there are $n-1$ edges (but no cycle) then if edge e is not taken in the MST then MST will not be connected.

edited by
35 votes
35 votes

Option A is correct.

a

Here, in this example we can easily see that B, C, D are false. So, B,C,D are not always true.

  that's why A is always true..  A (Ans)

14 votes
14 votes
Option a is always true

Option b is not true when e is not part of a cycle.

Option c is not true when e is part of a cycle and all edge weights are same in that cycle

Option d is need not be true when e is not part of a cycle

Option a is always true as only the min weight edge in a cut set will be part of a minimum spanning tree.
3 votes
3 votes

(A) True, because if there is heaviest edge in MST, then there exist a cut with all edges with weight equal to heaviest edge.

(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.

Answer:

Related questions

25 votes
25 votes
3 answers
4
Ishrat Jahan asked Nov 3, 2014
8,917 views
What is the output printed by the following program?#include <stdio.h int f(int n, int k) { if (n == 0) return 0; else if (n % 2) return f(n/2, 2*k) + k; else return f(n/...