AFTD Auto-Formalizing Theoretical Domains

op223_star_connectivity_from_edge_preservation

theoremverified

Assume shifting along a nonsustainable edge preserves it, shifting a branch toward the center of a nonsustainable pendant edge preserves that edge, and every vertex of a non-star tree has a non-leaf neighbor. Then every nonsustainable finite tree with at least two vertices reaches a star through nonsustainable generalized tree shifts.

Statement

theorem op223_star_connectivity_from_edge_preservation
    (halong : ∀ (n : ℕ) (T : SimpleGraph (Fin n)) (u v : Fin n),
      T.IsTree → T.Adj u v → ¬ is_sustainable_edge T s(u,v) →
        ¬ is_sustainable_edge (gts_graph T u v u) s(u,v))
    (hpend : ∀ (n : ℕ) (T : SimpleGraph (Fin n)) (u v w : Fin n),
      T.IsTree → T.Adj u w → Nat.card (T.neighborSet w) = 1 →
      ¬ is_sustainable_edge T s(u,w) → T.Adj u v →
        ¬ is_sustainable_edge (gts_graph T u v u) s(u,w))
    (hcenter : ∀ (n : ℕ), 2 ≤ n → ∀ (T : SimpleGraph (Fin n)), T.IsTree →
      ¬ Nonempty (T ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) →
      ∀ u : Fin n, ∃ v, T.Adj u v ∧ 2 ≤ Nat.card (T.neighborSet v)) :
    ∀ (n : ℕ), 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
arXiv:2610.17078 Open Problem 6.1
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • op223_star_connectivity_of_nonleaf_rank_stepIf 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…
  • op223_nonsustainable_has_bad_edgeEvery nonsustainable finite tree contains an edge that is not sustainable.
  • op223_tree_adjacent_shift_nonleaf_countIf both endpoints of an edge of a finite tree have degree at least two, shifting along that edge reduces the number of non-leaf vertices…
  • op223_shift_bad_edge_yields_stepIf a nonsustainable tree undergoes an adjacent shift and a retained beneficiary edge remains nonsustainable, the shift is a step between…
  • 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.
  • is_sustainable_edgeAn edge e in a tree T is sustainable if there exists a non-edge f such that T - e + f is a tree and the adjacency spectral radius of T - e…
  • is_nonsustainable_treeA tree T is non-sustainable if T is a tree and T is not sustainable.
  • is_generalized_tree_shiftA simple graph T' on an arbitrary type V is obtained from a tree T by a generalized tree shift if T is a tree, and there exist distinct…
  • gts_graphThe graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between…
  • is_sustainable_treeA tree T is sustainable if every edge of T is sustainable.

The proof, explained

The theorem is proved by induction on the number of non-leaf vertices in the tree, using op223_star_connectivity_of_nonleaf_rank_step to reduce the problem to showing that any nonsustainable tree that is not a star can take a nonsustainable generalized tree shift step that strictly decreases its non-leaf count. Since the tree is nonsustainable, it contains a nonsustainable edge s(a, b). If both endpoints are non-leaves, shifting along the edge itself preserves its nonsustainability by assumption halong and strictly decreases the non-leaf count. If at least one endpoint is a leaf, assumption hcenter supplies an adjacent non-leaf neighbor to shift along, and assumption hpend ensures that shifting preserves the nonsustainability of the pendant edge, again strictly decreasing the non-leaf count.

  1. To prove star connectivity, it suffices to show that any nonsustainable tree that is not a star can take a nonsustainable generalized tree shift step to another nonsustainable tree with strictly fewer non-leaf vertices.

    Applying the reduction lemma op223_star_connectivity_of_nonleaf_rank_step, the global reachability to a star graph is reduced by induction to finding a single step that strictly decreases the number of non-leaves (vertices of degree greater than 1). We fix a tree T on n ≥ 2 vertices, assuming T is nonsustainable and not isomorphic to a star graph.

    lines 17–19

    uses op223_star_connectivity_of_nonleaf_rank_step

      classical
      apply op223_star_connectivity_of_nonleaf_rank_step
      intro n hn T hT hstar
  2. The tree T contains an edge s(a, b) that is not sustainable.

    By op223_nonsustainable_has_bad_edge, every nonsustainable tree has at least one edge that fails to be sustainable.

    line 20

    uses op223_nonsustainable_has_bad_edge

      obtain ⟨a, b, hab, hbad⟩ := op223_nonsustainable_has_bad_edge T hT
  3. Every vertex with at least one neighbor has strictly positive degree.

    If u is adjacent to v, its neighbor set contains v and is thus non-empty. By Nat.card_pos, any non-empty finite set has strictly positive cardinality.

    lines 21–23

    uses Nat.card_pos

      have hpos (u v : Fin n) (huv : T.Adj u v) : 0 < Nat.card (T.neighborSet u) := by
        letI : Nonempty (T.neighborSet u) := ⟨⟨v, huv⟩⟩
        exact Nat.card_pos
  4. Shifting between adjacent non-leaf vertices while preserving a nonsustainable edge yields a valid nonsustainable generalized tree shift step that strictly reduces the non-leaf count.

    Suppose u and v are adjacent vertices each of degree at least 2, and w is a neighbor of u such that the shifted graph Y = gts_graph T u v u keeps the edge s(u, w) nonsustainable. By op223_shift_bad_edge_yields_step, T → Y is a valid nonsustainable generalized tree shift step. Furthermore, by op223_tree_adjacent_shift_nonleaf_count, performing this shift between adjacent non-leaf vertices reduces the count of non-leaf vertices by exactly 1, so the number of non-leaves in Y is strictly less than in T.

    lines 24–33

    uses op223_shift_bad_edge_yields_step, op223_tree_adjacent_shift_nonleaf_count

      have hmake (u v w : Fin n) (huv : T.Adj u v) (huw : T.Adj u w)
          (hu2 : 2 ≤ Nat.card (T.neighborSet u)) (hv2 : 2 ≤ Nat.card (T.neighborSet v))
          (hbad' : ¬ is_sustainable_edge (gts_graph T u v u) s(u,w)) :
          ∃ Y : SimpleGraph (Fin n), is_nonsustainable_tree Y ∧ nonsustainable_gts_step T 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 (T.neighborSet x))).card := by
        have hs := op223_shift_bad_edge_yields_step T hT u v w huv huw hbad'
        refine ⟨gts_graph T u v u, hs.2.1, hs, ?_⟩
        have hc := op223_tree_adjacent_shift_nonleaf_count T u v hT.1 huv hu2 hv2
        omega
  5. If T contains a nonsustainable pendant edge s(u, w) with leaf w, there exists a valid non-leaf-reducing nonsustainable shift step.

    Since T is not a star, hypothesis hcenter provides a neighbor v of u with degree at least 2. Because w has degree 1 while v has degree at least 2, w ≠ v. Since u has at least two distinct neighbors w and v (using Fintype.one_lt_card_iff.mpr, congrArg, Subtype.val, and Nat.card_eq_fintype_card), its degree is at least 2. By hypothesis hpend, shifting v toward u preserves the nonsustainability of s(u, w). Having two adjacent non-leaves u and v whose shift preserves the nonsustainable edge s(u, w), we invoke the helper from the previous step to produce the desired non-leaf-reducing step.

    lines 34–53

    uses Fintype.one_lt_card_iff.mpr, congrArg, Subtype.val, Nat.card_eq_fintype_card

      have hpendstep (u w : Fin n) (huw : T.Adj u w)
          (hw1 : Nat.card (T.neighborSet w) = 1)
          (hbadw : ¬ is_sustainable_edge T s(u,w)) :
          ∃ Y : SimpleGraph (Fin n), is_nonsustainable_tree Y ∧ nonsustainable_gts_step T 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 (T.neighborSet x))).card := by
        obtain ⟨v, huv, hv2⟩ := hcenter n hn T hT.1 hstar u
        have hwv : w ≠ v := by
          intro h
          subst v
          omega
        have hu2 : 2 ≤ Nat.card (T.neighborSet u) := by
          have hp : 1 < Fintype.card (T.neighborSet u) := by
            apply Fintype.one_lt_card_iff.mpr
            refine ⟨⟨w, huw⟩, ⟨v, huv⟩, ?_⟩
            intro hh
            exact hwv (congrArg Subtype.val hh)
          have hp' : 1 < Nat.card (T.neighborSet u) := by rw [Nat.card_eq_fintype_card]; exact hp
          omega
        exact hmake u v w huv huw hu2 hv2 (hpend n T u v w hT.1 huw hw1 hbadw huv)
  6. When both endpoints of the nonsustainable edge have degree at least 2, there is a valid non-leaf-reducing shift.

    We split into cases on whether deg(a) ≥ 2. In the branch where both deg(a) ≥ 2 and deg(b) ≥ 2, we shift along the edge s(a, b) itself (setting u = a and v = w = b). By hypothesis halong, shifting along a nonsustainable edge preserves its nonsustainability, so the helper from Step 4 applies directly.

    lines 54–56

      by_cases ha : 2 ≤ Nat.card (T.neighborSet a)
      · by_cases hb : 2 ≤ Nat.card (T.neighborSet b)
        · exact hmake a b b hab hab ha hb (halong n T a b hT.1 hab hbad)
  7. When a has degree at least 2 but b has degree 1, there is a valid non-leaf-reducing shift.

    If deg(a) ≥ 2 but deg(b) < 2, then since b is adjacent to a, its degree is positive and thus exactly 1. Hence b is a leaf, and the pendant edge helper from Step 5 applies to u = a and w = b.

    lines 57–58

        · have hb1 : Nat.card (T.neighborSet b) = 1 := by have := hpos b a hab.symm; omega
          exact hpendstep a b hab hb1 hbad
  8. When a has degree 1, there is a valid non-leaf-reducing shift, completing the induction step.

    If deg(a) < 2, then as a is adjacent to b, its degree is strictly positive and therefore deg(a) = 1. By symmetry of unordered pairs (Sym2.eq_swap), the edge s(b, a) is identical to s(a, b) and is therefore nonsustainable. The pendant edge helper from Step 5 applies to u = b and w = a, completing the case analysis and establishing the induction step.

    lines 59–63

    uses Sym2.eq_swap

      · have ha1 : Nat.card (T.neighborSet a) = 1 := by have := hpos a b hab; omega
        have hbad' : ¬ is_sustainable_edge T s(b,a) := by
          rw [Sym2.eq_swap]
          exact hbad
        exact hpendstep b a hab.symm ha1 hbad'
op223_star_connectivity_of_nonleaf_rank_step
If every nonsustainable tree that is not a star can take a nonsustainable generalized tree shift step to another nonsustainable tree with strictly fewer non-leaf vertices, then every nonsustainable tree can reach a star graph through nonsustainable generalized tree shifts.
op223_nonsustainable_has_bad_edge
Every nonsustainable tree contains at least one edge that is not sustainable.
Nat.card_pos
Any non-empty finite type has strictly positive cardinality.
op223_shift_bad_edge_yields_step
Shifting an adjacent edge in a nonsustainable tree while keeping an edge nonsustainable produces a valid nonsustainable generalized tree shift step.
op223_tree_adjacent_shift_nonleaf_count
In a tree, shifting between two adjacent vertices that each have degree at least 2 decreases the number of non-leaf vertices by exactly 1.
Fintype.one_lt_card_iff.mpr
A finite type has cardinality strictly greater than 1 if it contains at least two distinct elements.
congrArg
Applying a function to equal inputs yields equal outputs (a₁ = a₂ implies f(a₁) = f(a₂)).
Subtype.val
The canonical projection extracting the underlying element from a subtype.
Nat.card_eq_fintype_card
For any finite type, its cardinality as a natural number equals its cardinality given by its Fintype instance.
Sym2.eq_swap
Swapping the components of an unordered pair leaves the pair unchanged: s(a, b) = s(b, a).

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 SimpleGraphtheorem op223_star_connectivity_from_edge_preservation    (halong : ∀ (n : ℕ) (T : SimpleGraph (Fin n)) (u v : Fin n),      T.IsTree → T.Adj u v → ¬ is_sustainable_edge T s(u,v) →        ¬ is_sustainable_edge (gts_graph T u v u) s(u,v))    (hpend : ∀ (n : ℕ) (T : SimpleGraph (Fin n)) (u v w : Fin n),      T.IsTree → T.Adj u w → Nat.card (T.neighborSet w) = 1 →      ¬ is_sustainable_edge T s(u,w) → T.Adj u v →        ¬ is_sustainable_edge (gts_graph T u v u) s(u,w))    (hcenter : ∀ (n : ℕ), 2 ≤ n → ∀ (T : SimpleGraph (Fin n)), T.IsTree →      ¬ Nonempty (T ≃g completeBipartiteGraph (Fin 1) (Fin (n - 1))) →      ∀ u : Fin n, ∃ v, T.Adj u v ∧ 2 ≤ Nat.card (T.neighborSet v)) :    ∀ (n : ℕ), 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  apply op223_star_connectivity_of_nonleaf_rank_step  intro n hn T hT hstar  obtain ⟨a, b, hab, hbad⟩ := op223_nonsustainable_has_bad_edge T hT  have hpos (u v : Fin n) (huv : T.Adj u v) : 0 < Nat.card (T.neighborSet u) := by    letI : Nonempty (T.neighborSet u) := ⟨⟨v, huv⟩⟩    exact Nat.card_pos  have hmake (u v w : Fin n) (huv : T.Adj u v) (huw : T.Adj u w)      (hu2 : 2 ≤ Nat.card (T.neighborSet u)) (hv2 : 2 ≤ Nat.card (T.neighborSet v))      (hbad' : ¬ is_sustainable_edge (gts_graph T u v u) s(u,w)) :      ∃ Y : SimpleGraph (Fin n), is_nonsustainable_tree Y ∧ nonsustainable_gts_step T 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 (T.neighborSet x))).card := by    have hs := op223_shift_bad_edge_yields_step T hT u v w huv huw hbad'    refine ⟨gts_graph T u v u, hs.2.1, hs, ?_⟩    have hc := op223_tree_adjacent_shift_nonleaf_count T u v hT.1 huv hu2 hv2    omega  have hpendstep (u w : Fin n) (huw : T.Adj u w)      (hw1 : Nat.card (T.neighborSet w) = 1)      (hbadw : ¬ is_sustainable_edge T s(u,w)) :      ∃ Y : SimpleGraph (Fin n), is_nonsustainable_tree Y ∧ nonsustainable_gts_step T 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 (T.neighborSet x))).card := by    obtain ⟨v, huv, hv2⟩ := hcenter n hn T hT.1 hstar u    have hwv : w ≠ v := by      intro h      subst v      omega    have hu2 : 2 ≤ Nat.card (T.neighborSet u) := by      have hp : 1 < Fintype.card (T.neighborSet u) := by        apply Fintype.one_lt_card_iff.mpr        refine ⟨⟨w, huw⟩, ⟨v, huv⟩, ?_⟩        intro hh        exact hwv (congrArg Subtype.val hh)      have hp' : 1 < Nat.card (T.neighborSet u) := by rw [Nat.card_eq_fintype_card]; exact hp      omega    exact hmake u v w huv huw hu2 hv2 (hpend n T u v w hT.1 huw hw1 hbadw huv)  by_cases ha : 2 ≤ Nat.card (T.neighborSet a)  · by_cases hb : 2 ≤ Nat.card (T.neighborSet b)    · exact hmake a b b hab hab ha hb (halong n T a b hT.1 hab hbad)    · have hb1 : Nat.card (T.neighborSet b) = 1 := by have := hpos b a hab.symm; omega      exact hpendstep a b hab hb1 hbad  · have ha1 : Nat.card (T.neighborSet a) = 1 := by have := hpos a b hab; omega    have hbad' : ¬ is_sustainable_edge T s(b,a) := by      rw [Sym2.eq_swap]      exact hbad    exact hpendstep b a hab.symm ha1 hbad'
See it in the graphDiscuss this resultChallenge it