Prune and search Algorithm for Generating a Bottleneck Spanning Tree
Let $b$ is the bottleneck edge of $MBST$, and let $b$ has weight $w(b)$.
Suppose $e_{m}$ is the median weighted edge of $G$, and let $e_{m}$ has weight $w(e_{m})$. Suppose $G$ gets partitioned into two subgraphs $G_{1}$ and $G_{2}$ such that edges in $G_{1}$ have weight $\leq w(e_{m})$ and edges in $G_{2}$ have weight $&gt; w(e_{m})$.
If $w(b) \leq w(e_{m})$, then there must exist an $MBST$ within $G_{1}$ itself. Since the algorithm is recursing on $G_{1}$, it will output an $MBST$ if it exists. If the algorithm does not output a valid spanning tree, it means $b \notin G_{1}$. In other words, $b \in G_{2}$.
In that case, the algorithm will update $e_{m}$ to be the median weight edge of $G_{2}$. The graph $G$ will again get partitioned into two subgraphs $G_{1}$ and $G_{2}$. And, the algorithm can repeat this process.