op223_nonsustainable_has_bad_edge
Every nonsustainable finite tree contains an edge that is not sustainable.
Statement
theorem op223_nonsustainable_has_bad_edge {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (hT : is_nonsustainable_tree T) : ∃ u v : V, T.Adj u v ∧ ¬ is_sustainable_edge T s(u, v)
- Source
- arXiv:2610.17078 Open Problem 6.1
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_nonsustainable_treeA tree T is non-sustainable if T is a tree and T is not sustainable.
- 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_sustainable_treeA tree T is sustainable if every edge of T is sustainable.
- 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
By definition, a tree is nonsustainable if it is not sustainable, whereas sustainability requires every edge in the tree to be sustainable. Consequently, a nonsustainable tree must have at least one edge that fails to be sustainable. Decomposing this edge into its endpoints as an unordered pair yields the required adjacent vertices.
Not every edge of T is sustainable.
By definition, a tree is nonsustainable if it is a tree and is not a sustainable tree. Since a sustainable tree is defined as a tree in which every edge is sustainable, assuming all edges of T were sustainable would contradict the assumption that T is nonsustainable.
classical have hbad : ¬ ∀ e ∈ T.edgeSet, is_sustainable_edge T e := by intro h exact hT.2 ⟨hT.1, h⟩
There exists an edge e in T that is not sustainable.
Pushing the negation through the universal quantifier produces an edge e ∈ T.edgeSet such that e is not sustainable.
push_neg at hbad obtain ⟨e, he, hnot⟩ := hbad
There exist adjacent vertices u and v such that the edge between them is not sustainable.
By induction on the symmetric square using Sym2.ind, the edge e can be written as an unordered pair s(u, v) of vertices u, v ∈ V. The edge membership s(u, v) ∈ T.edgeSet is definitionally the adjacency T.Adj u v, so the pair u, v witnesses the existential goal.
uses
Sym2.indinduction e using Sym2.ind with | _ u v => exact ⟨u, v, he, hnot⟩
Sym2.ind- Every element of the symmetric square Sym2 α is an unordered pair s(x, y) for some x, y : α.
- In SimpleGraph, the adjacency relation T.Adj u v is definitionally identical to the membership s(u, v) ∈ T.edgeSet, so the edge membership hypothesis directly proves adjacency.
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_nonsustainable_has_bad_edge {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) (hT : is_nonsustainable_tree T) : ∃ u v : V, T.Adj u v ∧ ¬ is_sustainable_edge T s(u, v) := by classical have hbad : ¬ ∀ e ∈ T.edgeSet, is_sustainable_edge T e := by intro h exact hT.2 ⟨hT.1, h⟩ push_neg at hbad obtain ⟨e, he, hnot⟩ := hbad induction e using Sym2.ind with | _ u v => exact ⟨u, v, he, hnot⟩