Past exam of the short options course of the University of Oxford / 2017 / 7

A tree is a connected graph with no cycles. Equivalently, between any two of its vertices there is exactly one graph path. A single vertex with no edges is also a tree.

A shortest path from $u$ to $v$ is a graph path $P$ joining these endpoints such thatfor every other $uv$-path $P^{\prime }$ in $G$, where $w(P)$ is the sum of its edge weights. Here paths have no repeated vertices; minimizing over unrestricted walks is a different problem when negative edge weights occur.

A shortest-path tree rooted at $v$ is a spanning tree $T$ of $G$ for which the unique $vu$-path in $T$ is a $w$-shortest $vu$-path in $G$ for every vertex $u$. It simultaneously realizes all distances from the root. It need not be a minimum spanning tree, which minimizes total tree weight instead.

Use a triangle with vertices $v,a,b$ and weights $w(va)=w(vb)=2$, $w(ab)=-1$. The unique shortest $va$-path is $v,b,a$, of weight one, while the unique shortest $vb$-path is $v,a,b$, also of weight one. A shortest-path tree would therefore need all three edges of the triangle. This is impossible for a tree.

Thus negative edge weights can prevent a shortest-path tree, even though the shortest simple path to each individual vertex exists. This is the example in signed edge weights can prevent a shortest-path tree.

Under the usual walk convention allowing repeated edges, the stated hypothesis is insufficient. Take the connected graph consisting of one zero-weight edge $xy$. It has no simple cycles, so the cycle condition holds. Nevertheless $Q=x,y,x,y$ is a minimum-weight $xy$-walk of weight zero and is not a path.

If the course uses “walk” to mean an edge-nonrepeating trail, the intended argument is valid. If such a minimum trail repeats a vertex, take its first repeated-vertex segment. Its interior vertices are distinct and no edge repeats, so this segment is a simple cycle $C$. Removing it leaves an $xy$-trail of weight $w(Q)-w(C)<w(Q)$, a contradiction. Hence $Q$ is a path. Since every $xy$-path is a competing trail, it is a shortest path.

For unrestricted walks, the same proof works if every nontrivial closed subwalk has positive weight, in particular if every edge has positive weight. This is cycle erasure in minimum-weight walks. The exact 2017 course convention was not available to check; the counterexample and the trail interpretation distinguish the two meanings explicitly.

Let $d(u)$ be the weight of a shortest $vu$-path, and let $p(u)$ be the predecessor of $u$ on the chosen $P_u$. Its prefix to $p(u)$ must also be shortest: a cheaper prefix followed by the final edge would give a cheaper walk to $u$, and cycle erasure in minimum-weight walks would produce a cheaper path because every edge weight is positive. ThereforeFollowing predecessor arrows strictly decreases $d$, so cannot revisit a vertex. Since each nonroot vertex has a predecessor, finiteness forces every predecessor chain to end at $v$. Thus $T$ is connected.

The edges $e_u$ are distinct: if two vertices selected the same undirected edge, each would be the other's predecessor, contradicting strict decrease. Hence $T$ has exactly $|V(G)|-1$ edges. A finite connected graph with this edge count is a tree. This proves that positive-weight shortest-path predecessors form a tree, without requiring the initially chosen paths to be mutually consistent.

The unique root-to-$u$ path in $T$ is the reversal of its predecessor chain. Every edge satisfies $w(e_z)=d(z)-d(p(z))$. Summing along that chain telescopes tosince $d(v)=0$ for positive weights. Thus the tree path is a shortest $vu$-path in $G$ for every $u$, and $T$ is a shortest-path tree rooted at $v$.