retagged by
11,652 views
20 votes
20 votes

Let $G$ be a connected undirected weighted graph. Consider the following two statements.

  • $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$.
  • $S_2$: If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning tree.

Which one of the following options is correct?

  1. Both $S_1$ and $S_2$ are true
  2. $S_1$ is true and $S_2$ is false
  3. $S_1$ is false and $S_2$ is true
  4. Both $S_1$ and $S_2$ are false
retagged by

6 Answers

Best answer
11 votes
11 votes
We can think of running the Kruskals algorithm for finding the Minimum Spanning Tree on graph $G.$

While doing that, we sort the edges based on their weight and start selecting edges from the smallest weight $(w_{\text{small}}$ for example).

Problem with $S_1$:  If we have multiple copies of $w_{\text{small}}$, then a specific $w_{\text{small}}$ weighted edge is not guaranteed to be selected by Kruskals algorithm.

$S_2$ is Correct: If the sorted order of the edges contains only distinct values, Kruskals algorithm will always select a unique set of edges resulting in a unique minimum spanning tree.

Correct option: C.
selected by
13 votes
13 votes
S1 is false -->If G has all edges with equal weight , then not possible,

S2 is true
2 votes
2 votes

S1: “There exists a minimum weight edge in G”

There can be two interpretations of this statement-

1) There exists a specific minimum weight edge which must be present in all minimum spanning trees of the graph.

2) There exists atleast one minimum weight edge which is present in every minimum spanning trees of the graph.

In either case S1 will be false statement. Let me prove this using two examples.

For case 1

 

Here edge AB is not present in two of the possible minimum spanning trees.

For case 2

Here no edge is common between the two possible minimum spanning trees of the graph. That is there does not exist atleast 1 edge which is present in the two possible spanning trees.

So we can clearly state that Statement 1 is False.

S2: “If every edge in G has distinct weight, then G has a unique minimum spanning tree.”

This statement is obvious since if edge weights are distinct there will always be a distinct edge set and only 1 minimum spanning tree possible. Which is True

Correct Answer C

edited by
1 votes
1 votes

Since in S1 its not mentioned about the uniqueness of weights, assume in the graph where all edges have equal weights, then all the weights are minimum and not all minimum weights are included in spanning tree. Hence S1 is false.

 

In S2 all the edge weights are unique this means only 1 possible combination is there for making the spanning tree. Hence true.

So option C is correct

Answer:

Related questions

8 votes
8 votes
3 answers
1
Arjun asked Feb 18, 2021
10,695 views
Consider the following undirected graph with edge weights as shown:The number of minimum-weight spanning trees of the graph is ___________.