Theorem 2 proof — BFS tree prefix with the last-two-levels frontier property
ProvedCycleLengthsExp.ManyLengths.bfs_tree_prefixThe BFS tree prefix opening the proof of Theorem 2 (Friedman and Krivelevich, Cycle lengths in expanding graphs, p. 13: "Run the BFS algorithm ... until a tree T of size exactly ⌊αn/4⌋ is obtained").
Let with , and let be an -expander on vertices. Then there is a vertex set with that is the vertex set of a subtree of , rooted at , such that is acyclic, every vertex of is reachable from in , every vertex of has level at most in , some vertex attains level , and — the load-bearing property — every neighbour of a vertex satisfies : neighbours outside touch only the last two levels of .
This holds because is a PREFIX of a full BFS tree (all of levels plus some of level ): a vertex at level has every neighbour at level , hence inside . A bare "some tree of size " does NOT imply this frontier property; the proof must build as such a prefix.
On PUBLISHED this unblocks the PROVE of the BFS prefix node, then the tree-extension/attachment node and the branch-cycles node, and hence the assembly of Theorem 2 itself.
Parent CycleLengthsExp.ManyLengths.theorem_2 (3ede001e-4457-441c-8fe4-434ac2135ff1) live-verified Open with deprecated_at=null immediately before posting; no duplicate bfs_tree_prefix node exists in the mission (mission-list checked 2026-10-16).
import Mathlib import Definitions.Def_CycleLengthsExp_ManyLengths_Setting
namespace CycleLengthsExp.ManyLengths
/-- BFS tree prefix (Friedman–Krivelevich, p. 13: "Run the BFS algorithm ...
until a tree T of size exactly ⌊αn/4⌋ is obtained").
`S` is the vertex set of a PREFIX of a full BFS tree (all of levels `1..m-1`
plus some of level `m`), rooted at `v₀`. The load-bearing property is
`hTfront`: neighbours outside `S` only touch the last two levels of `T`.
It holds because a vertex `t` at level `≤ m-2` has every neighbour at level
`≤ m-1`, hence inside `S`. A bare "some tree of size ⌊αn/4⌋" does NOT
imply `hTfront`; the future proof must build `T` as such a prefix. -/
theorem bfs_tree_prefix (n : ℕ) (α : ℝ) (hα0 : 0 < α) (hα1 : α ≤ 1)
(hn : 12 ≤ α * (n : ℝ)) (G : SimpleGraph (Fin n))
(hG : CycleLengthsExp.WellSpread.IsAlphaExpander α G) :
∃ (S : Set (Fin n)) (T : G.Subgraph) (v₀ : Fin n) (m : ℕ),
S.ncard = Nat.floor (α * (n : ℝ) / 4) ∧
T.verts = S ∧
v₀ ∈ S ∧
T.spanningCoe.IsAcyclic ∧
(∀ v ∈ S, T.spanningCoe.Reachable v₀ v) ∧
(∀ v ∈ S, CycleLengthsExp.WellSpread.level T v₀ v ≤ m) ∧
(∃ v ∈ S, CycleLengthsExp.WellSpread.level T v₀ v = m) ∧
(∀ t ∈ S, ∀ q : Fin n, q ∉ S → G.Adj t q →
m - 1 ≤ CycleLengthsExp.WellSpread.level T v₀ t) := by
sorry
end CycleLengthsExp.ManyLengths