Past exam of the short options course of the University of Oxford / 2021 / 7 (Graph theory)

For a finite connected graph, a spanning tree contains every graph vertex and is connected and acyclic. A minimum spanning tree minimizes ${\sum }_{e\in E(T)}w(e)$ over all such trees. A shortest-path tree rooted at $v$ is a spanning tree whose unique $v$-to-$u$ graph path has length $d_G(v,u)$ for every graph vertex $u$. Here the weighted path length is the sum of its edge weights. The two optimizations generally differ, as (b) shows. Connectedness is needed for either spanning-tree object to exist.

For the grid, Kruskal's algorithm examines edges in nondecreasing order of weight and accepts an edge exactly when it joins two different components of the current forest. The weights are encountered in the orderThe horizontal and vertical acceptance rules are detailed in the two numbered subanswers. Together they produceThere are $(n-1)(n+2)/2$ horizontal and $n(n-1)/2$ vertical edges, totaling $n^2-1$. Every accepted edge attaches a previously isolated graph vertex to the component already built, so the result is connected and acyclic. The correctness theorem for Kruskal's algorithm, which follows from the minimum spanning tree cut property, proves minimality. Its total cost isFor $n=1$ the tree has one graph vertex, no edges and cost zero. The source's numbered items specify the two edge types; the following subanswers record their contributions to the algorithm.

At weight $y$ the edges considered are precisely the horizontal edges in row $y$. For $y=1$ all $n$ graph vertices in that row are isolated, so all $n-1$ edges are accepted. For $y\ge 2$, the first $y-1$ graph vertices in that row already belong to the one component built by earlier stages, because vertical columns $1,\dots ,y-1$ have already been processed. The other graph vertices are isolated. Thus the edges with $x<y-1$ would create a graph cycle, and all the edges with $x\ge y-1$ are accepted, successively attaching the remaining graph vertices. The rule isThe selected edges of equal weight have no cycles after the existing component is contracted, so tie ordering does not affect this conclusion. Their combined contribution to the minimum spanning tree cost is

At weight $x+1/2$, column $x$ is considered just after horizontal row $x$. At this point its first $x$ graph vertices already lie in the component built so far, while graph vertices above them in that column are isolated. Consequently vertical edges with $y<x$ create a graph cycle, while those with $y\ge x$ attach the isolated graph vertices in a chain:Together with the horizontal rule this gives an induction on the alternating row and column stages and justifies the component description used in both numbered answers. The vertical contribution to the minimum spanning tree cost is

Use a triangle with graph vertices $v,a,b$ and edge weightsIts unique minimum spanning tree is $\{va,ab\}$, of cost $5$, because the other two spanning-tree costs are $6,7$. In this tree the $v$-to-$b$ graph path has length $2+3=5$, whereas the edge $vb$ gives length $4$ in the original graph. ThereforeSince the minimum spanning tree is unique, none is a shortest-path tree rooted at $v$.

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$.