Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S2: If every

Question

Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which one of the following options is correct?

Both S1 and S2 are true

S1 is true and S2 is false.

S1 is false and S2 is true.

Both S1 and S2 are false
No, the answer is incorrect.
Score: 0
Accepted Answers:
S1 is false and S2 is true.
Gate Mock Test, Gate Practice Test question, Answer carefully with all clear steps and accuracy with given answer:15) Let be. connected unrected weighted graph, Consider the follwing two ststements pont
51: Thee exists a minimum weight adge in G wich presant in svry minimum spamg ee of G.
2 evry ecg 1G has distinct weight hen § 12 qs in Spam ee
Which one the following options i conect?
Both $1 and S2 are rue
STs ue and s2 is fase.
Ss alse and S215 true.
Both 51 and 52 are fase.
No, the answer is incorrect
Score: 0
Accepted Answers:
EIRe—

VIPSolutions · Accepted Answer

Let's analyze both statements carefully:

---

## Statement S1:
**"There exists a minimum weight edge in G which is present in every minimum spanning tree (MST) of G."**

- **Claim:** There is at least one *minimum weight* edge that **must** be in **every** MST.

- **Counterexample:**  
  Consider a graph with two edges of the same minimum weight connecting the same vertices, or a situation where multiple MSTs exist with different edges, none of which necessarily include the same minimum weight edge.  
  In general, **it's possible** that no single minimum weight edge appears in **every** MST.

- **Conclusion:**  
  S1 is **not necessarily true**.

---

## Statement S2:
**"If every edge in G has distinct weight, then G has a unique minimum spanning tree."**

- This is a well-known property of MSTs:  
  When all edges have **distinct weights**, the MST is **unique**.

- **Therefore:**  
  S2 is **true**.

---

## Final answer:
- S1 is **false**.
- S2 is **true**.

**Correct option:**  
**"S1 is false and S2 is true."**

---

## Summary:
| Statement | True/False | Explanation |
|--------------|--------------|--------------|
| S1 | False | No guarantee of a minimum weight edge being in **every** MST. |
| S2 | True | Unique MST when all edge weights are distinct. |

---

**Answer:**
**S1 is false and S2 is true.**

✨ VIPSolutions

Question:

Final Answer:

📢 Instructions:

Study Help, Fast Answers

✨ VIPSolutions

Question:

Final Answer:

📢 Instructions:

Related Answers

Study Help, Fast Answers