Past exam of the short options course of the University of Oxford / 2023 / 7 / b

There is an index slip in the source: starting with $G_1$ and performing steps $1,\dots ,n$ produces the final graph $G_{n+1}$. Write $H$ for that final graph. The literal assertion for $G_n$ can fail: take a triangle with $\ell (xz)=3$, $\ell (xy)=2$, $\ell (yz)=1$. Before the final step the extra edge $yz$ remains; only the final deletion removes it.

The invariant is that $x$ and $y$ remain connected. Choose a simple $xy$ graph path $P$ in $H$. If an edge of $H$ did not lie in $P$, then at its processing time $P$ was still present and avoided that edge. The algorithm would therefore have deleted it, a contradiction. Thus every edge of $H$ lies in $P$. The final graph is precisely an $xy$ path and possibly isolated vertices.

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

Take a minimum spanning tree $T$, for example one constructed by Kruskal's algorithm. Fix $v$ and let $e$ be a longest edge of the tree's unique $xv$ path. Deleting $e$ partitions $T$ into two components separating $x$ and $v$. Any alternative $xv$ path crosses this graph cut. If all of its edges were shorter than $e$, a crossing edge $f$ would let us replace $e$ by $f$, producing a spanning tree of smaller total length. This contradicts minimality of $T$.

Therefore every competing path has an edge at least as long as $e$, and the tree path solves the bottleneck shortest path problem. The same minimum spanning tree works simultaneously for every $v$; this is the minimax path property of a minimum spanning tree.