edited by
3,168 views
31 votes
31 votes

Let $G = (V,E)$ be an undirected connected simple (i.e., no parallel edges or self-loops) graph with the weight function $w: E \rightarrow \mathbb{R}$ on its edge set. Let $w(e_{1}) < w(e_{2}) < · · · < w(e_{m})$, where $E = \left\{e_{1}, e_{2}, . . . , e_{m}\right\}$. Suppose $T$ is a minimum spanning tree of $G$. Which of the following statements is FALSE?

  1. The tree $T$ has to contain the edge $e_{1}$.
  2. The tree $T$ has to contain the edge $e_{2}$.
  3. The minimum weight edge incident on each vertex has to be present in $T$.
  4. $T$ is the unique minimum spanning tree in $G$.
  5. If we replace each edge weight $w_{i} = w(e_{i})$ by its square $w^{2}_{i}$ , then $T$ must still be a minimum spanning tree of this new instance.
edited by

1 Answer

Best answer
43 votes
43 votes

Answer is E. The catch here is edge-weights belongs to real number. Therefore, edge weight can be negative. In that case the minimum spanning tree may be different.

  • $e1$= $-5$
  • $e2=1$
  • $e3=2$

 

$T$ is: 

New edge weights:

  • $e1= 25$
  • $e2=1$
  • $e3=4$

 

EDIT:

(Here every edge weight is distinct, therefore MST is unique.)

Option A is True. If we apply Kruskal's algorithm, it will choose $e_1$

Option B is True. If we apply Kruskal's algorithm then it will also choose $e_2$, and $2$ edges can not form a cycle. ($e_3$ is not guaranteed in MST, as it may form a cycle)

Option C is also true. If we apply Prims algorithm also on any vertex (say u), it chooses minimum

weight edge incident on vertex u.

Option D is true. Because every edge weight is distinct. 

edited by
Answer:

Related questions