# GATE2019-38

5.9k views

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

edited
1
number of ways to distribute k similar objects to n distinct set is : (n + k - 1)Ck

answer : (2+10-1)C10 * (2+15-1)C15 * (2+14-1)C14 = 2640.
0
For option 1 this is contradicting statement
1
Note that, it is used " if " in the statement but not " if and only if "
0
The claim should be true iff it is true for all graphs.
1

Even if the graph has multiple edges with same weight graph has unique MST

3
i am not getting what you want to deliver,

in the question they are saying,

if all edge weights are unique, then G has unique minimum spanning tree. ---- TRUE

Converse :-  If G has unique minimum spanning tree, then all edge weights are unique. ----- False
1
You are talking about the reverse implication -- not the given statement
0
got it.sorry for the inconvenience
1
no need of sorry, it's just a discussion !
3

@Arjun

why the following is not a counter example for second statement:

The cut has minimum unique weight but multiple MSTs.

1
You have to consider every possible cut sets as per the given statement.
0
@arjun why cut set and why not cut edge?
0

@Digvijay Pandey could you please the counter example given by sunil.

0
cut means cut set but not the cut edge !
0
the line is

"if for every cut of G ,there is a unique minimum weight edge crossing the cut,=> then G has a unique minimum spanning tree"
0

Cut set is the set of edges whose removal disconnect the connected graph..so do you not think that cut is also same as cut set and it is min cut set??

@Shaik Masthan

0

4

@Sankha Narayan Bose

e1 and e2 also a cutset, then is this diagram satisfying conditions mentioned in the question ?

0

@Shaik Masthan

I donot think it is telling about cut set. Because, if it is a cut set then can cut more than one edge, which is violation of spanning tree

right?

https://en.wikipedia.org/wiki/Cut_(graph_theory)

0

@Sankha Narayan Bose

Actually they are telling to remove minimum edge from a graph, (which they described as cut set)

And after that removal, is it forming a MST? As minimum edge edge is unique , so it forming a unique spanning tree

0
Here they did not mention cut set..cut canbe bridge also..but if we can find atleast one counter example then is not it that statement can not be true..

Please let me know if my understanding is correct
1

@srestha They are asking about the original graph not the ones you get after cutting.

4
They mean for any cut of the graph. Now what is a cut. Any partition of vertices of graph forms a cut. And for every cut if we choose the min edge passing that cut, then that gives us the mst of graph. Now they hv asked if this min for each cut is unique which implies we have a unique mst, so it's true.
2

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

1

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.

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.

edited
5
It's a direct question from CLRS textbook, page number 630, Question 23.1-6. Another reason to do Exercise problems of standard text books :)
1

This example can be used to prove that converse of statement II is not true.  Cut is ({A,C},{B,D}).

The Minimum spanning tree is unique, however there are two minimum weight edges (A,B) and (A,D) having same weight crossing this cut.

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

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
If for every cut of a graph there is a unique minimum weight edge crossing the cut,
then the graph has a unique minimum spanning tree.

This statement is true and can be proved ea sily by contradiction.
1 vote

Explanation:

Given G be a connected, weighted and undirected graph,
I. TRUE: G Graph is unique, no two edges of the graph is same.

Step-1: Using Kruskal's algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step-2:

Step-3: 17 + 18 + 20 + 21 + 22 + 23 + 26 = 147
Step-4: Here, all the elements are distinct. So, the possible MCST is 1.
II. TRUE: As per the above graph, if we are cut the edge, that should the be the minimum edge.
Because we are already given, all minimum edge weights if graph is distinct.

–1 vote

If edge wt. are distinct then the graph will have unique MST but the converse of this statement (statement 1 of question) is not true.

The graph can have unique MST even though it has repeated edge weights.

So, statement 1 is False.

## Related questions

1
6.2k 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}$
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$.
An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a connected, undirected graph that contains no cycle. A $\text{leaf}$ in a tree is a vertex that has degree ... $u \in V_1$ and v$\in V_2$ or vice versa. Prove that if $G$ is a tree with at least two vertices, then $G$ is bipartite.
Let $G$ be an arbitrary graph on $n$ vertices with $4n − 16$ edges. Consider the following statements: There is a vertex of degree smaller than $8$ in $G$. There is a vertex such that there are less than $16$ vertices at a distance exactly $2$ from it. Which of the following is true: I Only II Only Both I and II Neither I nor II