Proof of `A shortest path can wait longer`
groundedproofs/Lax330177Proofs/CostExamples.lean · lax-330177
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Without the shortcut, every path from 0 to 2 must traverse both arcs of the chain. Departing at times 0 and 3 therefore gives a shortest path, but it waits at vertex 1 from time c until time 3. Departing instead at 0 and c removes that positive wait while keeping both traversals. This second path both waits less and finishes sooner, for c equal to zero or one.