op223_star_connectivity_from_edge_preservation
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.
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.
uses
op223_star_connectivity_of_nonleaf_rank_stepclassical apply op223_star_connectivity_of_nonleaf_rank_step intro n hn T hT hstar
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.
uses
op223_nonsustainable_has_bad_edgeobtain ⟨a, b, hab, hbad⟩ := op223_nonsustainable_has_bad_edge T hTEvery 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.
uses
Nat.card_poshave 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
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.
uses
op223_shift_bad_edge_yields_step,op223_tree_adjacent_shift_nonleaf_counthave 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
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.
uses
Fintype.one_lt_card_iff.mpr,congrArg,Subtype.val,Nat.card_eq_fintype_cardhave 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)
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.
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)
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.
· have hb1 : Nat.card (T.neighborSet b) = 1 := by have := hpos b a hab.symm; omega exact hpendstep a b hab hb1 hbad
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.
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).
- The proof uses `omega` for several simple arithmetic deductions regarding vertex degrees, such as deducing that a vertex with at least one neighbor and not at least two neighbors must have degree exactly 1.
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 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'