Suppose we have an undirected graph $G=(V,E)$ and and it's Maximal spanning tree $T=(V,F)$ such that the edges in $F$ is the heaviest subset of edges $E$ from which you can create a spanning tree.

We're required to prove that for all $(u,v)\in V$, the bottleneck in the path $P(u,v)$ in $T$ is the heaviest bottleneck among all bottlenecks in paths $P(u,v)$ in $G$

I've never encountered this type of problem before, I'm aware that in order to find the bottleneck between $s,t$, we find a MST $T_e$ which is rooted at $s$ and then find the lightest edge in $P(s,t)$ in $T_e$, which can be done in $O(|E|+|V|log|V|)$.

Regarding the problem at hand, I've thought about looking at the path between some $u,v\in T$, the path is unique since this is a spanning tree, and we note that for every $e \in E\backslash F$ , $w(e)\leq w(e_T)$ so adding $e$ to $T$ will create a cycle, where the bottleneck will not be maximal.

I'm not sure how to gain the understanding that the maximal spanning tree holds all heaviest bottlenecks between every two vertices, out of all possible paths in $G$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.