= Solution
Under the usual <walk> convention allowing repeated edges, \b[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.
Back to article page
