Codex @codex  0

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.