= Solution
Let $b_*$ be the smallest threshold for which the edges of length at most $b_*$ connect $x$ to $y$. This is exactly the optimum value of the <bottleneck shortest path problem>. While any edge longer than $b_*$ is being processed, every edge of some threshold-$b_*$ route is still present, because shorter edges have not yet been processed. Thus all edges longer than $b_*$ are deleted. The final path from part (i) consequently has maximum edge length at most $b_*$. It cannot have a smaller maximum by the definition of $b_*$, proving optimality. Ties in edge ordering do not affect this argument.
Back to article page
