Context
PathGraphDist.lean proves that the graph-theoretic distance in a path graph equals the absolute difference of vertex indices:
pathGraph_dist (n : ℕ) (i j : Fin n) : (pathGraph n).dist i j = |i - j|
This fills a gap in Mathlib's SimpleGraph.Connectivity.PathGraph API, which defines path graph adjacency but not distance. The edist variant is also proved.
What needs to happen
- Check Mathlib's current state — confirm
pathGraph_dist doesn't exist yet (it didn't as of Lean 4.28.0)
- Post to Zulip (
#graph-theory) proposing the addition, linking to fd-formalization
- Refactor to Mathlib style — the proof may need adjustments for Mathlib's naming conventions, docstrings, and universe polymorphism requirements
- Submit PR to
Mathlib.Combinatorics.SimpleGraph.Connectivity.PathGraph (or wherever reviewers suggest)
- AI disclosure per Mathlib policy
Prior art
SimpleGraph.ball (PR #36443) followed this exact pipeline: develop in fd-formalization → Zulip discussion → Mathlib PR. PathGraphDist is the second upstream candidate.
Acceptance criteria
Context
PathGraphDist.leanproves that the graph-theoretic distance in a path graph equals the absolute difference of vertex indices:This fills a gap in Mathlib's
SimpleGraph.Connectivity.PathGraphAPI, which defines path graph adjacency but not distance. Theedistvariant is also proved.What needs to happen
pathGraph_distdoesn't exist yet (it didn't as of Lean 4.28.0)#graph-theory) proposing the addition, linking to fd-formalizationMathlib.Combinatorics.SimpleGraph.Connectivity.PathGraph(or wherever reviewers suggest)Prior art
SimpleGraph.ball(PR #36443) followed this exact pipeline: develop in fd-formalization → Zulip discussion → Mathlib PR. PathGraphDist is the second upstream candidate.Acceptance criteria