Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2017/7/c/solution

Under the usual walk convention allowing repeated edges, the stated hypothesis is insufficient. Take the connected graph consisting of one zero-weight edge . It has no simple cycles, so the cycle condition holds. Nevertheless is a minimum-weight -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 . Removing it leaves an -trail of weight , a contradiction. Hence is a path. Since every -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.

New to topics? Read the docs here!