op223_path_connectivity_of_leaf_rank_step
If every sustainable tree X on Fin n (n ≥ 1) that is not a path has a sustainable generalized-tree-shift predecessor Y with strictly fewer leaves, then every sustainable tree on Fin n is reachable from a path by a sequence of sustainable generalized tree shifts.
Statement
theorem op223_path_connectivity_of_leaf_rank_step (hstep : ∀ (n : ℕ) (_hn : 1 ≤ n) (X : SimpleGraph (Fin n)), is_sustainable_tree X → ¬ Nonempty (X ≃g SimpleGraph.pathGraph n) → ∃ Y : SimpleGraph (Fin n), is_sustainable_tree Y ∧ sustainable_gts_step Y X ∧ (Finset.univ.filter (fun x : Fin n => Nat.card (Y.neighborSet x) = 1)).card < (Finset.univ.filter (fun x : Fin n => Nat.card (X.neighborSet x) = 1)).card) : ∀ (n : ℕ) (_hn : 1 ≤ n) (X : SimpleGraph (Fin n)), is_sustainable_tree X → ∃ P : SimpleGraph (Fin n), Nonempty (P ≃g SimpleGraph.pathGraph n) ∧ Relation.ReflTransGen sustainable_gts_step P X
- Source
- step towards op223_gts_poset_connectivity
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_sustainable_treeA tree T is sustainable if every edge of T is sustainable.
- sustainable_gts_stepA transition step between two sustainable trees T and T' on a finite type V where T' is obtained from T by a generalized tree shift.
The proof, explained
The theorem is proved by strong induction on the number of leaves of a sustainable tree X. If X is already isomorphic to a path graph, it is reachable from itself in zero steps. Otherwise, the step hypothesis provides a sustainable predecessor tree Y with strictly fewer leaves from which X can be obtained in one generalized tree shift; by the induction hypothesis, Y is reachable from a path graph, and appending the step Y → X yields reachability from that path graph to X.
Fix an integer n ≥ 1 and define the leaf rank of a graph on n vertices.
We enable classical logic, fix the graph size n with 1 ≤ n, and define `rank X` as the number of vertices in X that have degree 1 (the leaves of the tree).
classical intro n hn let rank (X : SimpleGraph (Fin n)) := (Finset.univ.filter (fun x : Fin n => Nat.card (X.neighborSet x) = 1)).card
By strong induction on the leaf rank k, it suffices to show that every sustainable tree with k leaves is reachable from a path graph.
We formulate an auxiliary lemma `go` stating that every sustainable tree X with `rank X = k` can be reached from a path graph by sustainable generalized tree shifts. We prove this by strong induction on k using `Nat.strong_induction_on`, obtaining an induction hypothesis (`ih`) for all trees with strictly fewer than k leaves, and introduce a tree X with `rank X = k`.
uses
Nat.strong_induction_onhave go : ∀ k : ℕ, ∀ X : SimpleGraph (Fin n), is_sustainable_tree X → rank X = k → ∃ K : SimpleGraph (Fin n), Nonempty (K ≃g SimpleGraph.pathGraph n) ∧ Relation.ReflTransGen sustainable_gts_step K X := by intro k induction k using Nat.strong_induction_on with | h k ih => intro X hX hRank
If X is already isomorphic to a path graph, it is reachable from a path graph in zero steps.
We perform a case split on whether X is isomorphic to `pathGraph n`. When it is (`hstar`), X itself serves as the witness path graph, reachable from itself in zero steps by reflexivity (`Relation.ReflTransGen.refl`).
uses
Relation.ReflTransGen.reflby_cases hstar : Nonempty (X ≃g SimpleGraph.pathGraph n) · exact ⟨X, hstar, Relation.ReflTransGen.refl⟩
If X is not isomorphic to a path graph, it is reachable from a path graph via a predecessor with strictly fewer leaves.
When X is not a path graph, the hypothesis `hstep` provides a sustainable predecessor tree Y such that `sustainable_gts_step Y X` holds and Y has strictly fewer leaves than X, so `rank Y < k`. Applying the induction hypothesis (`ih`) to Y yields a path graph K reaching Y. Appending the step from Y to X via `Relation.ReflTransGen.tail` shows that K reaches X.
uses
Relation.ReflTransGen.tail· obtain ⟨Y, hY, hXY, hlt⟩ := hstep n hn X hX hstar have hsmall : rank Y < k := by simpa [rank, ← hRank] using hlt obtain ⟨K, hK, hYK⟩ := ih (rank Y) hsmall Y hY rfl exact ⟨K, hK, Relation.ReflTransGen.tail hYK hXY⟩
The inductive lemma specializes to any arbitrary sustainable tree X.
Given an arbitrary sustainable tree X, we instantiate the auxiliary lemma `go` with k = `rank X` and the trivial equality `rank X = rank X`, completing the proof.
intro X hX exact go (rank X) X hX rfl
Nat.strong_induction_on- Strong (complete) mathematical induction on natural numbers: to prove a property for all natural numbers, it suffices to prove it for n assuming it holds for all m < n.
Relation.ReflTransGen.refl- The reflexive-transitive closure of a relation is reflexive: any element is related to itself in zero steps.
Relation.ReflTransGen.tail- A sequence of steps in the reflexive-transitive closure can be extended on the right by a single step of the relation.
- The relation `Relation.ReflTransGen sustainable_gts_step P X` represents the reflexive-transitive closure, meaning that graph X can be obtained from graph P by a finite sequence of zero or more sustainable generalized tree shifts.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open SimpleGraph/-- Reduction of the sustainable half to a one-step leaf-count drop. -/theorem op223_path_connectivity_of_leaf_rank_step (hstep : ∀ (n : ℕ) (_hn : 1 ≤ n) (X : SimpleGraph (Fin n)), is_sustainable_tree X → ¬ Nonempty (X ≃g SimpleGraph.pathGraph n) → ∃ Y : SimpleGraph (Fin n), is_sustainable_tree Y ∧ sustainable_gts_step Y X ∧ (Finset.univ.filter (fun x : Fin n => Nat.card (Y.neighborSet x) = 1)).card < (Finset.univ.filter (fun x : Fin n => Nat.card (X.neighborSet x) = 1)).card) : ∀ (n : ℕ) (_hn : 1 ≤ n) (X : SimpleGraph (Fin n)), is_sustainable_tree X → ∃ P : SimpleGraph (Fin n), Nonempty (P ≃g SimpleGraph.pathGraph n) ∧ Relation.ReflTransGen sustainable_gts_step P X := by classical intro n hn let rank (X : SimpleGraph (Fin n)) := (Finset.univ.filter (fun x : Fin n => Nat.card (X.neighborSet x) = 1)).card have go : ∀ k : ℕ, ∀ X : SimpleGraph (Fin n), is_sustainable_tree X → rank X = k → ∃ K : SimpleGraph (Fin n), Nonempty (K ≃g SimpleGraph.pathGraph n) ∧ Relation.ReflTransGen sustainable_gts_step K X := by intro k induction k using Nat.strong_induction_on with | h k ih => intro X hX hRank by_cases hstar : Nonempty (X ≃g SimpleGraph.pathGraph n) · exact ⟨X, hstar, Relation.ReflTransGen.refl⟩ · obtain ⟨Y, hY, hXY, hlt⟩ := hstep n hn X hX hstar have hsmall : rank Y < k := by simpa [rank, ← hRank] using hlt obtain ⟨K, hK, hYK⟩ := ih (rank Y) hsmall Y hY rfl exact ⟨K, hK, Relation.ReflTransGen.tail hYK hXY⟩ intro X hX exact go (rank X) X hX rfl