ISI2022 - MCS - PCB - Math | Question: 8

Question

Let $G:=(V, E)$ be a simple, connected, undirected, weighted graph with vertex set $V,|V| \geq 4$, and edge set $E,|E| \geq 4$. The edges have distinct positive weights on them. Prove that a minimum spanning tree of $G$ either contains the edge with the third smallest weight or the edge with the fourth smallest weight.

Answer 1

1. if u go with kruskalls algorithm. it automatically chooses starts from the lowest edges. first smallest edge is selected by default. second smallest edge is selected automatically bcoz it doesnt disobey the principle of a spanning tree. since this is a connected graph. worst case scenario. the third lowest edge is between the three vertices forming a cycle. so the fourth one is chosen.

Hence third or fourth lowest is chosen always

can anyone tell me how you would prove it with prims algo