IIT Bombay PhD exam paper

Question

Suppose G is a complete undirected graph with 5 vertices (K5) whose 10 edges are given distinct edge weights from 1...10. Let MST(G) be a minimum weight spanning tree of G. Then MST(G) must contain edges with the following weights (i)_____ (fill ALL such weights).

MST(G) cannot contain edges with the following weights (ii)_________ (fill ALL such weights).

Comments

We have 5 nodes. Say E1 joins N1 and N2. E2 joins N2 and N3. Now, it might happen E3 will join E1 and E3. Hence, E3 might not get included. 1 and 2 should be because they will always connect 3 different nodes.

I drew a graph and I guess 8,9,10 will never get included because till you draw 7 edges. All nodes will be connected.

Not sure though

---

Ashwin we can say about 1,2 but not 4.. since they might form cycle so we lose 4.

---

Ohh yes I thought bit wrong 4 can also form cycle.