AFTD Auto-Formalizing Theoretical Domains

op223_star_connectivity_of_nonleaf_rank_step

theoremverified

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

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.

  1. 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).

    lines 13–16

      classical
      intro n hn
      let rank (X : SimpleGraph (Fin n)) :=
        (Finset.univ.filter (fun x : Fin n => 1 < Nat.card (X.neighborSet x))).card
  2. 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.

    lines 17–23

    uses Nat.strong_induction_on

      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
  3. 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).

    lines 24–25

    uses Relation.ReflTransGen.refl

          by_cases hstar : Nonempty (X ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1)))
          · exact ⟨X, hstar, Relation.ReflTransGen.refl⟩
  4. 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.

    lines 26–29

    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⟩
  5. 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.

    lines 30–31

      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

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
See it in the graphDiscuss this resultChallenge it