Register

GATE CSE 2019 | Question: 38

• retagged by
20,483 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
User Avatar

6 Answers

3 votes
3 votes
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.
User Avatar
–1 votes
–1 votes

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.

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

33 votes
33 votes
14 answers
1
Arjun asked Feb 7, 2019
21,272 views
GATE CSE 2019 | Question: 12
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}$
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}...
User Avatar
1 votes
1 votes
1 answer
3
akash.dinkar12 asked Apr 8, 2019
888 views
ISI2017-PCB-CS-1(b)
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$.
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$.
User Avatar
Link Copied!