11,847 views
37 votes
37 votes

Let $w$ be the minimum weight among all edge weights in an undirected connected graph. Let $e$ be a specific edge of weight $w$. Which of the following is FALSE?

  1. There is a minimum spanning tree containing $e$

  2. If $e$ is not in a minimum spanning tree $T$, then in the cycle formed by adding $e$ to $T$, all edges have the same weight.

  3. Every minimum spanning tree has an edge of weight $w$

  4. $e$ is present in every minimum spanning tree

3 Answers

Best answer
45 votes
45 votes

D is the false statement.

A minimum spanning tree must have the edge with the smallest weight (In Kruskal's algorithm we start from the smallest weight edge). So, C is TRUE.

If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must have weight $\leq e$, as otherwise we can interchange that edge with $e$ and get another minimum spanning tree of lower weight. So, B and A are also TRUE.

D is false because, suppose a cycle is there with all edges having the same minimum weight $w$. Now, any one of them can be avoided in any minimum spanning tree. 

edited by
Answer:

Related questions

64 votes
64 votes
15 answers
1
Arjun asked Jul 6, 2016
36,697 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...
29 votes
29 votes
2 answers
2