Lemma 3.1 — a path is shortest iff a 1-Lipschitz integer potential increases along it
ProvedMetricMSO.lemma_3_1fixed-parameter-tractabilitygraph-theorymonadic-second-order-logicp2o-gran-per-chapterp2o-plan-paperp2o-v1treewidth
Let be a path in with and . Then is a shortest - path if and only if there is a map with
This is the integer form of the certificate, which the following statements replace by finite labels.
Differences from the source:
- encoding: the path P = v₀…v_r → a walk p with Walk.IsPath, r = p.length and vᵢ = p.getVert i; reason: the same object
Preamble
import Mathlib
Formal statement
namespace MetricMSO
/-- **Lemma 3.1.** Chakraborty, Ordyniak, Siebertz (arXiv:2610.41974, sha256 prefix ad3c5863), p.20 (PDF 22): "Let P = v0v1 · · · vr be a
path in G, with s = v0 and t = vr. The following statements are equivalent. (a) P is a shortest s-t
path. (b) There exists a map λ: V(G) → Z such that |λ(u) − λ(v)| ≤ 1 for every uv ∈ E(G), (3)
λ(vi+1) = λ(vi) + 1 for every 0 ≤ i < r. (4)"
**Formalization Note** `P` is a walk with `Walk.IsPath`, `r` its length, `vᵢ` is `p.getVert i`.
"Shortest" is `p.length = G.dist s t`; `G.dist` is the true distance because `p` joins `s` and
`t`. -/
theorem lemma_3_1 {V : Type} [Fintype V] (G : SimpleGraph V) {s t : V} (p : G.Walk s t)
(hp : p.IsPath) :
p.length = G.dist s t ↔
∃ lam : V → ℤ, (∀ u v, G.Adj u v → |lam u - lam v| ≤ 1) ∧
∀ i, i < p.length → lam (p.getVert (i + 1)) = lam (p.getVert i) + 1 := by sorry
end MetricMSO
Source
Chakraborty, Ordyniak, Siebertz, Model Checking for Metric Extensions of MSO (arXiv:2610.41974, sha256 ad3c586330b037548a2b4a977081284996698f39c1b55c17b91cb81a536d3dd9), Lemma 3.1, p.20 (PDF 22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.