Past exam of the short options course of the University of Oxford / 2021 / 7 / c

Assume throughout (c) that the graph is finite and connected, as needed for the asserted spanning trees. List its edge weights as $w_1<\cdots <w_m$. The stated separation implies $w_{j+1}>2w_j$, so for every $k$,Thus the weights form a superincreasing sequence. If $A,B$ are distinct edge sets, let $e$ be the heaviest edge in their symmetric difference. Suppose $e\in A$. All other uncancelled edges are lighter, soTherefore different edge sets have different total costs. In particular all distinct spanning trees have different costs. Since a finite connected graph has at least one spanning tree and only finitely many choices,This domination of every collection of smaller edges will also be used in (iii).

By (i), two simple graph paths with different edge sets have different lengths. In particular two distinct simple graph paths from the fixed root $v$ to the same graph vertex $u$ have different edge sets, so there is a unique shortest graph path from $v$ to each $u$. Positive weights ensure that a shortest walk has no repeated graph vertex: removing a graph cycle strictly reduces its length.

For each $u\ne v$, take the final edge of its unique shortest graph path. Every initial segment of a shortest graph path is itself shortest, since replacing it by a shorter one would shorten the whole route. Thus these edges agree with the graph paths' unique predecessors. Following a predecessor strictly decreases $d_G(v,u)$, so no predecessor graph cycle is possible, and all graph vertices eventually connect to $v$. They form a shortest-path tree. Every other such tree would have to use the same unique root-to-vertex graph paths, provingLiteral wording qualification. “Any two paths” needs a convention. Reversing an undirected graph path preserves its edge set and length; distinct zero-edge graph paths at different graph vertices also have length zero. Thus the unrestricted statement is false if these count as different graph paths. The proved edge-set assertion, and in particular uniqueness for graph paths with the same ordered endpoints, is exactly what is needed for the deduction. Arbitrary walks are not included.

Let $T$ be the unique minimum spanning tree. If $e=ab$ is an edge outside $T$, adding it creates a unique graph cycle consisting of $e$ and the tree graph path $P_T(a,b)$. Every edge $f$ on that graph path has $w(f)<w(e)$: otherwise the distinct weights would give $w(f)>w(e)$, and replacing $f$ by $e$ would produce a cheaper spanning tree. This is the minimum spanning tree cycle property in exchange form.

By the domination inequality in (i), it follows more strongly thatNow consider any simple graph path $P$ from $v$ to $u$ that is not the tree graph path. It must use an edge outside $T$. Replace every such edge by the corresponding tree graph path. Each replacement strictly reduces length and produces a walk entirely in $T$. Removing any repeated-vertex excursions leaves the unique tree graph path $P_T(v,u)$ and can only reduce length further. ThereforeSo every root-to-vertex graph path in $T$ is the unique shortest graph path in $G$, andThe argument works for every choice of root $v$.