AFTD Auto-Formalizing Theoretical Domains

op223_path_connectivity_of_leaf_rank_step

theoremverified

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.

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

    lines 13–16

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

    lines 17–23

    uses Nat.strong_induction_on

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

    lines 24–25

    uses Relation.ReflTransGen.refl

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

    lines 26–29

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

    lines 30–31

      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.

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