Graph Theory

Question

Consider the following undirected graph with some edge costs missing.

Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold?

1. $cost(a,b)\geq 6$.
2. $cost(b,e)\geq 5$.
3. $cost(e,f)\geq 5$.
4. $cost(a,d)\geq 4$.
5. $cost(b,c)\geq 4$.

Please someone solve and explain :)

Comments

apply Kruskal algo for every option and check if it is satisfying the the minimum spanning tree or not

answer is d) because if cost(a,d) is 4 then (a,d) will be in minimum spanning tree rather than (d,e) and we want (d,e) so option d need not hold

Answer 1

option d

if you put the cost of enequalities then  minimum cost spanning tree must be a all weavy edges.

then we put the  cost of edges one by one if mst is only weavy edges then it is right otherwise it is wrong

Comments

Thanks :)