retagged by
20,275 views
40 votes
40 votes

Let $G$ be any connected, weighted, undirected graph.

  1. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight.
  2. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut.

Which of the following statements is/are TRUE?

  1. I only
  2. II only
  3. Both I and II
  4. Neither I nor II
retagged by

6 Answers

Best answer
26 votes
26 votes

1. If edge weights are distinct then there exist unique MST.

2. If for every cut of a graph there is a unique light edge crossing the cut then the graph has a unique minimum spanning tree but converse may not be true.

Proof by contradiction:
Lemma: If an edge $e$ is contained in some minimum spanning tree, then it is a minimum cost edge crossing some cut of the graph.

Assume MST is not unique and there exist two MST's  $T_1$ and $T_2$
Suppose $e_1∈T_1$ but $e_1 \notin T_2$, if we remove $e_1$ from $T_1$, then we will have disconnected graph with two set of vertices $V_1$ and $V_2$. According to lemma $e_1$ is a minimum cost edge in the cut between $V_1$ and $V_2$.

Suppose $e_2∈T_2$ but $e_2 \notin T_1$, if we remove $e_2$ from $T_2$, then we will have disconnected graph with two set of vertices $V_1$ and $V_2$. According to lemma $e_2$ is a minimum cost edge in the cut between $V_1$ and $V_2$.

Because the minimum cost edge is unique implies $e_1$ and $e_2$ is the same edge. $e_1 \in T_2$ and $e_2 \in T_1$. We have chosen $e_1$ at random, of all edges in $T_1$, also in $T_2$ and same for $e_2$. As a result, the MST is unique.

Why converse is not true always? 

https://stanford.edu/~rezab/discrete/Midterm/midtermsoln.pdf

So both statements in the question are TRUE.

Answer is (C).

edited by
30 votes
30 votes

Statement 1 : True

Statement 2 : True. Explanation below.

For this I have an intuitive approach. This is not a formal mathematical proof but it occurred to me after thinking for quite some time. 

Please point it out if you think something is wrong.

edited by
14 votes
14 votes

Statement 1 is true. Proof can be found easily.


The biggest confusion in Statement 2 is what is a cut? Is it cut set, or cut vertex, or cute edge?

Actually, a cut is anything that creates a partition, or "cut" in the set of vertices $V$ of a graph.

cut $C=(S,T)$ is a partition of $V$ of a graph $G=(V,E)$ into two subsets S and T.

Notice "cut" is actually a set of two subsets.

One might say that cut is a cut set.

So, if for every cut set of a graph, there exists a unique minimum weight edge; then graph has a unique MST. True.

Why? Because the whole graph can be seen as the collection of these cut sets and from each cut set we can only pick the unique minimum weight edge.


 

Option C; both the statements are true.


 

Let G be a connected, undirected graph. A cut in G is a set of edges whose removal...

These wordings are taken from GATE 1999, Question Number 5.

edited by
7 votes
7 votes
Both the statements are true.

Statement (I) is based on how Kruskal’s algorithm works.

Statement (II) is based on how Prism’s algorithm works.

[Check the working/algorithm of each of them in CLRS and you can easily conclude that the two statements are two.]

Kruskal MST algorithm works by first sorting the edges in non-decreasing order of their weights. Then it chooses the edges taken in sorted order and adds them to the MST which the algorithm is forming if the edge being added does not form a cycle with the edges already in the MST in progress. Now if all the edge weights are distinct then while choosing an edge, Kruskal’s algorithm will not have any choice and the MST formed shall be unique.

Prim’s MST algorithm, works on the concept of cut. During its working it maintains two sets say $S$ [which contains the vertices included in the MST being formed] and the set $V[G]-S$ , which contains the vertices not yet incorporated in the MST being formed. Now set $S$ and $V[G]-S$ at each instant forms a cut. The algorithm works by incorporating the edge having the minimum edge weight between the two set $S$ and $V[G]-S$ and including it along with its end vertex $v$ in $V[G]$ into $S$. Now if every cut of the graph $G$ has unique edge weights, Prim’s algorithm shall not find options while choosing this edge.
Answer:

Related questions

32 votes
32 votes
14 answers
1
Arjun asked Feb 7, 2019
20,982 views
Let $G$ be an undirected complete graph on $n$ vertices, where $n 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to$n!$$(n-1)!$$1$$\frac{(n-1)!}{2}...
1 votes
1 votes
1 answer
3
akash.dinkar12 asked Apr 8, 2019
846 views
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.