While this submission is a draft, it cannot be used by other submissions.

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.

Read the Lean proof on GitHub

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.