op223_star_connectivity_of_nonleaf_rank_step
If every non-sustainable tree X on Fin n (n ≥ 2) that is not a star has a non-sustainable generalized-tree-shift successor Y with strictly fewer non-leaf vertices, then every non-sustainable tree on Fin n reaches a star by a sequence of non-sustainable generalized tree shifts.
Statement
theorem op223_star_connectivity_of_nonleaf_rank_step (hstep : ∀ (n : ℕ) (_hn : 2 ≤ n) (X : SimpleGraph (Fin n)), is_nonsustainable_tree X → ¬ Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) → ∃ Y : SimpleGraph (Fin n), is_nonsustainable_tree Y ∧ nonsustainable_gts_step X Y ∧ (Finset.univ.filter (fun x : Fin n => 1 < Nat.card (Y.neighborSet x))).card < (Finset.univ.filter (fun x : Fin n => 1 < Nat.card (X.neighborSet x))).card) : ∀ (n : ℕ) (_hn : 2 ≤ n) (X : SimpleGraph (Fin n)), is_nonsustainable_tree X → ∃ K : SimpleGraph (Fin n), Nonempty (K ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) ∧ Relation.ReflTransGen nonsustainable_gts_step X K
- Source
- step towards op223_gts_poset_connectivity
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_nonsustainable_treeA tree T is non-sustainable if T is a tree and T is not sustainable.
- nonsustainable_gts_stepA transition step between two non-sustainable trees T and T' on a finite type V where T' is obtained from T by a generalized tree shift.
- Used by 1
- op223_star_connectivity_from_edge_preservationAssume shifting along a nonsustainable edge preserves it, shifting a branch toward the center of a nonsustainable pendant edge preserves…
The proof, explained
The theorem is proved by strong induction on the rank of the tree, defined as the number of non-leaf vertices (vertices of degree greater than 1). If a tree is already a star, it reaches a star trivially in zero steps. Otherwise, the step hypothesis provides a non-sustainable generalized tree shift to a tree with strictly lower rank, which reaches a star by the induction hypothesis; prepending this step completes the path.
Fix n ≥ 2 and define the rank of a tree on n vertices as its number of non-leaf vertices.
We enable classical reasoning and fix n along with the assumption 2 ≤ n. We define rank X as the number of vertices x in Fin n with degree strictly greater than 1 (the non-leaf vertices of X).
classical intro n hn let rank (X : SimpleGraph (Fin n)) := (Finset.univ.filter (fun x : Fin n => 1 < Nat.card (X.neighborSet x))).card
Formulate the induction claim that any non-sustainable tree of rank k reaches a star, and set up strong induction on k.
We introduce a helper lemma go stating that for any k ∈ ℕ and any non-sustainable tree X with rank X = k, X can reach a star graph completeBipartiteGraph (Fin 1) (Fin (n - 1)) via non-sustainable generalized tree shifts. We prove this by strong induction on k using Nat.strong_induction_on, yielding an induction hypothesis ih for all ranks m < k, and then introduce a tree X with rank k.
uses
Nat.strong_induction_onhave go : ∀ k : ℕ, ∀ X : SimpleGraph (Fin n), is_nonsustainable_tree X → rank X = k → ∃ K : SimpleGraph (Fin n), Nonempty (K ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) ∧ Relation.ReflTransGen nonsustainable_gts_step X K := 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 star graph, it reaches a star in zero steps.
We split into cases on whether X is isomorphic to completeBipartiteGraph (Fin 1) (Fin (n - 1)). If it is, K = X satisfies the goal immediately by reflexivity of the reflexive-transitive closure (Relation.ReflTransGen.refl).
uses
Relation.ReflTransGen.reflby_cases hstar : Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) · exact ⟨X, hstar, Relation.ReflTransGen.refl⟩
If X is not a star, taking one step gives a tree of strictly smaller rank that reaches a star by induction.
If X is not a star, the hypothesis hstep provides a non-sustainable tree Y reachable from X in one GTS step whose non-leaf count is strictly smaller than that of X. Since rank X = k, we have rank Y < k. Applying the induction hypothesis ih to Y yields a star K reachable from Y. Prepending the transition X → Y using Relation.ReflTransGen.head shows that X reaches K.
uses
Relation.ReflTransGen.head· 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.head hXY hYK⟩
Every non-sustainable tree on Fin n reaches a star graph.
Given any non-sustainable tree X, we apply the helper lemma go with k = rank X, establishing that X reaches a star graph.
intro X hX exact go (rank X) X hX rfl
Nat.strong_induction_on- The principle of strong induction on ℕ: to prove a property holds for all natural numbers, it suffices to prove it for n under the assumption that it holds for all m < n.
Relation.ReflTransGen.refl- Reflexivity of the reflexive-transitive closure: any element reaches itself in zero steps.
Relation.ReflTransGen.head- Prepending a single transition to a sequence of steps: if a reaches b in one step and b reaches c in zero or more steps, then a reaches c.
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 non-sustainable half to a one-step non-leaf-count drop. -/theorem op223_star_connectivity_of_nonleaf_rank_step (hstep : ∀ (n : ℕ) (_hn : 2 ≤ n) (X : SimpleGraph (Fin n)), is_nonsustainable_tree X → ¬ Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) → ∃ Y : SimpleGraph (Fin n), is_nonsustainable_tree Y ∧ nonsustainable_gts_step X Y ∧ (Finset.univ.filter (fun x : Fin n => 1 < Nat.card (Y.neighborSet x))).card < (Finset.univ.filter (fun x : Fin n => 1 < Nat.card (X.neighborSet x))).card) : ∀ (n : ℕ) (_hn : 2 ≤ n) (X : SimpleGraph (Fin n)), is_nonsustainable_tree X → ∃ K : SimpleGraph (Fin n), Nonempty (K ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) ∧ Relation.ReflTransGen nonsustainable_gts_step X K := by classical intro n hn let rank (X : SimpleGraph (Fin n)) := (Finset.univ.filter (fun x : Fin n => 1 < Nat.card (X.neighborSet x))).card have go : ∀ k : ℕ, ∀ X : SimpleGraph (Fin n), is_nonsustainable_tree X → rank X = k → ∃ K : SimpleGraph (Fin n), Nonempty (K ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) ∧ Relation.ReflTransGen nonsustainable_gts_step X K := by intro k induction k using Nat.strong_induction_on with | h k ih => intro X hX hRank by_cases hstar : Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) · 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.head hXY hYK⟩ intro X hX exact go (rank X) X hX rfl