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

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.