GATE Minimum Spanning Trees

Question

Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?

Comments

@Nidhi Budhraja

did you check my answer?

---

Yes, Thankyou

---

Yes done. Thanks again.

Answer 1

Minimum Spanning Tree means 

To cover all the nodes what is the minimum cost

 

let take this graph.

What is the Minimum Spanning tree cost?

10, tree is D-C-B-A

 

we know A-C is the shortest path but with that we only visit A and C

===> 10-7=3, did you can visit remaining vertices with this weight ?

Answer 2

 Consider the below graph.

 

MST is

(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

Shortest path from $1−4$ will be $7$ in MST but it should be $5$

Reference: https://cs.stackexchange.com/questions/18797/minimum-spanning-tree-vs-shortest-path