= Cycle erasure in minimum-weight walks
If every nontrivial closed subwalk has strictly positive weight, removing any repeated-vertex segment strictly decreases a <walk>'s weight. Hence a minimum-weight walk must be a <graph path>, and it is a <shortest path>. Strictly positive edge weights are sufficient in an undirected graph. For a <trail>, positivity of every simple <cycle> is already sufficient: its first repeated-vertex segment is a cycle because no edge is repeated.
Under the usual unrestricted <walk> convention, positivity of simple cycles alone is insufficient. A graph consisting of one zero-weight edge $xy$ has no cycles, but the walk $x,y,x,y$ is a minimum-weight walk and is not a path. A zero-weight backtrack cannot be removed with a strict improvement. For nonnegative edge weights, one may erase such backtracks without increasing weight and obtain a shortest path, but cannot conclude that every minimum walk was already a path.
Back to article page
