Lemma 2.5 — a path of length ℓ from a prescribed vertex
ProvedCycleLengthsExp.ManyLengths.lemma_2_5graph-pathsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vertex-expansion
Let and be positive integers, and let have more than vertices. Suppose every -element vertex set has at least external neighbors. If the connected component containing has at least vertices, then there is a simple path starting at with exactly edges:
This is the path-existence statement used before constructing the long path outside the initial tree in the proof of Theorem 2.
Formalization Note The component size is the number of vertices reachable from . The theorem formalizes the first assertion of Lemma 2.5; the subsequent “In particular” corollary is not a separate item here.
Preamble
import Mathlib import Definitions.Def_CycleLengthsExp_ManyLengths_Setting
Formal statement
namespace CycleLengthsExp.ManyLengths
/-- Friedman–Krivelevich, Lemma 2.5, p. 6, first assertion. -/
theorem lemma_2_5 {V : Type*} [Fintype V] (G : SimpleGraph V)
(k ℓ : ℕ) (hk : 0 < k) (hℓ : 0 < ℓ) (hV : k < Fintype.card V)
(hW : ∀ W : Set V, W.ncard = k → ℓ ≤ (CycleLengthsExp.WellSpread.extNbhd G W).ncard)
(v : V) (hv : k ≤ {w | G.Reachable v w}.ncard) :
∃ (w : V) (p : G.Walk v w), p.IsPath ∧ p.length = ℓ := by sorry
end CycleLengthsExp.ManyLengths
Source
Friedman and Krivelevich, Cycle lengths in expanding graphs, arXiv:1912.11011v2, p. 6, Lemma 2.5, first assertion (cited as Lemma 2.4 on p. 13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.