no_sustainable_tree_fin_two
No simple graph on the two-element vertex type Fin 2 is a sustainable tree: a tree there has one edge and the complement has no edge at all, so no edge of it can be sustained by a swap.
Statement
theorem no_sustainable_tree_fin_two (X : SimpleGraph (Fin 2)) : ¬ is_sustainable_tree X- Source
- step towards op223_poset_connectivity
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_sustainable_treeA tree T is sustainable if every edge of T is sustainable.
- is_tree_iff_is_acyclic_and_cardA simple graph G on a finite vertex type V is a tree if and only if G is acyclic and the number of edges plus 1 equals the number of…
- 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…
- adjacency_spectral_radiusThe adjacency spectral radius of a simple graph G on a finite vertex set is the spectral radius of its real adjacency matrix.
The proof, explained
Suppose for contradiction that $X$ is a sustainable tree on the two-element vertex type $\mathrm{Fin}\ 2$. A tree on two vertices has exactly $2 - 1 = 1$ edge, so there is an edge $e \in E(X)$, and sustainability guarantees a replacement edge $f \in E(X^c)$ in the complement graph. However, any two distinct vertices in $\mathrm{Fin}\ 2$ are either $0, 1$ or $1, 0$, so the existence of the edge $e$ means $0$ and $1$ are adjacent, leaving the complement graph $X^c$ completely empty. This contradicts the existence of $f$.
Assume for contradiction that $X$ is a sustainable tree on $\mathrm{Fin}\ 2$.
We unpack the hypothesis that $X$ is a sustainable tree into two parts: that $X$ is a tree (`hTree`), and that every edge of $X$ is sustainable (`hsus`), seeking to derive a contradiction (`False`).
rintro ⟨hTree, hsus⟩
There exist an edge $e \in E(X)$ and a complement edge $f \in E(X^c)$.
Since $X$ is a tree on $\mathrm{Fin}\ 2$, its edge count satisfies $|E(X)| + 1 = |\mathrm{Fin}\ 2| = 2$ by `is_tree_iff_is_acyclic_and_card`. Thus $|E(X)| = 1 > 0$, so the edge set is nonempty (`Nat.card_ne_zero.mp`) and contains some edge $e$. By definition of sustainability (`hsus e he`), there must exist a replacement edge $f$ in the complement graph $X^c$.
uses
is_tree_iff_is_acyclic_and_card,Nat.card_ne_zero.mphave hcard : Nat.card X.edgeSet + 1 = Nat.card (Fin 2) := (is_tree_iff_is_acyclic_and_card X).mp hTree |>.2 have h2 : Nat.card (Fin 2) = 2 := by simp have hpos : 0 < Nat.card X.edgeSet := by omega obtain ⟨⟨e, he⟩, -⟩ := Nat.card_ne_zero.mp hpos.ne' obtain ⟨f, hf, -⟩ := (hsus e he).2
Any two distinct vertices in $\mathrm{Fin}\ 2$ are adjacent in $X$ if and only if $0$ and $1$ are adjacent.
The only elements of $\mathrm{Fin}\ 2$ are $0$ and $1$. Exhaustive case analysis (`fin_cases`) on distinct vertices $a \neq b$ leaves only the ordered pairs $(0, 1)$ and $(1, 0)$. The pair $(0, 1)$ is trivially equivalent to $(0, 1)$ (`Iff.rfl`), while the pair $(1, 0)$ is equivalent by symmetry of graph adjacency (`SimpleGraph.adj_comm`).
uses
Iff.rfl,SimpleGraph.adj_commhave hkey : ∀ a b : Fin 2, a ≠ b → (X.Adj a b ↔ X.Adj 0 1) := by intro a b hab have ha : a = 0 ∨ a = 1 := by fin_cases a <;> simp have hb : b = 0 ∨ b = 1 := by fin_cases b <;> simp rcases ha with rfl | rfl <;> rcases hb with rfl | rfl · exact absurd rfl hab · exact Iff.rfl · rw [SimpleGraph.adj_comm] · exact absurd rfl hab
The edges $e$ and $f$ can be written as unordered pairs $s(a, b)$ and $s(c, d)$ for vertices $a, b, c, d \in \mathrm{Fin}\ 2$.
Every element of the symmetric square $\mathrm{Sym}^2(\mathrm{Fin}\ 2)$ is an unordered pair of vertices, so we perform induction on $e$ and $f$ using `Sym2.ind` to express them as $e = s(a, b) \in E(X)$ and $f = s(c, d) \in E(X^c)$.
uses
Sym2.indrevert he hf induction e using Sym2.ind with | h a b => induction f using Sym2.ind with | h c d => intro he hf
Contradiction: the vertices $c$ and $d$ must be both adjacent and non-adjacent in $X$.
Converting edge membership to adjacency (`SimpleGraph.mem_edgeSet`), $s(a, b) \in E(X)$ implies $a \neq b$ and $X.\mathrm{Adj}\ a\ b$. By the key equivalence, this implies $X.\mathrm{Adj}\ 0\ 1$. Since $s(c, d) \in E(X^c)$, the vertices are distinct ($c \neq d$); applying the equivalence in reverse yields $X.\mathrm{Adj}\ c\ d$. But being an edge of the complement graph means $c$ and $d$ are not adjacent in $X$ (`SimpleGraph.compl_adj`), giving the desired contradiction.
uses
SimpleGraph.mem_edgeSet,SimpleGraph.compl_adjrw [SimpleGraph.mem_edgeSet] at he hf have hab : a ≠ b := X.ne_of_adj he have hcd : c ≠ d := Xᶜ.ne_of_adj hf -- `X` is adjacent at `0,1`, while its complement is not. have h01 : X.Adj 0 1 := (hkey a b hab).mp he have hnc : ¬ X.Adj c d := ((SimpleGraph.compl_adj X c d).mp hf).2 exact hnc ((hkey c d hcd).mpr h01)
is_tree_iff_is_acyclic_and_card- A simple graph on a finite vertex set is a tree if and only if it is acyclic and the number of edges plus 1 equals the number of vertices.
Nat.card_ne_zero.mp- If the cardinality of a type is non-zero, then the type is nonempty.
Iff.rfl- Every proposition is logically equivalent to itself ($P \leftrightarrow P$).
SimpleGraph.adj_comm- Adjacency in a simple graph is symmetric: $u$ is adjacent to $v$ if and only if $v$ is adjacent to $u$.
Sym2.ind- Every element of the symmetric square $\mathrm{Sym}^2(\alpha)$ is an unordered pair $s(x, y)$ of elements of $\alpha$.
SimpleGraph.mem_edgeSet- An unordered pair $s(v, w)$ belongs to the edge set of a simple graph if and only if $v$ and $w$ are adjacent in the graph.
SimpleGraph.compl_adj- Two vertices are adjacent in the complement graph if and only if they are distinct and not adjacent in the original graph.
- The definition of `is_sustainable_tree` requires that for each tree edge $e$, there exists a complement edge $f$ such that deleting $e$ and adding $f$ yields a tree with spectral radius at least that of $X$. The proof only requires the existence of an edge in the complement graph $X^c$; the complement is completely empty, so the additional conditions on the swapped graph are never needed.
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.
/-- On Fin 2 the unique tree (a single edge) has empty complement edge set, hence is not sustainable; this makes the sustainable half of op223_poset_connectivity vacuous at n = 2. -/theorem no_sustainable_tree_fin_two (X : SimpleGraph (Fin 2)) : ¬ is_sustainable_tree X := by rintro ⟨hTree, hsus⟩ -- A tree on Fin 2 has exactly one edge. have hcard : Nat.card X.edgeSet + 1 = Nat.card (Fin 2) := (is_tree_iff_is_acyclic_and_card X).mp hTree |>.2 have h2 : Nat.card (Fin 2) = 2 := by simp have hpos : 0 < Nat.card X.edgeSet := by omega obtain ⟨⟨e, he⟩, -⟩ := Nat.card_ne_zero.mp hpos.ne' obtain ⟨f, hf, -⟩ := (hsus e he).2 -- On Fin 2 any two distinct vertices span the same single unordered pair, so all -- adjacencies between distinct vertices are equivalent to `X.Adj 0 1`. have hkey : ∀ a b : Fin 2, a ≠ b → (X.Adj a b ↔ X.Adj 0 1) := by intro a b hab have ha : a = 0 ∨ a = 1 := by fin_cases a <;> simp have hb : b = 0 ∨ b = 1 := by fin_cases b <;> simp rcases ha with rfl | rfl <;> rcases hb with rfl | rfl · exact absurd rfl hab · exact Iff.rfl · rw [SimpleGraph.adj_comm] · exact absurd rfl hab revert he hf induction e using Sym2.ind with | h a b => induction f using Sym2.ind with | h c d => intro he hf rw [SimpleGraph.mem_edgeSet] at he hf have hab : a ≠ b := X.ne_of_adj he have hcd : c ≠ d := Xᶜ.ne_of_adj hf -- `X` is adjacent at `0,1`, while its complement is not. have h01 : X.Adj 0 1 := (hkey a b hab).mp he have hnc : ¬ X.Adj c d := ((SimpleGraph.compl_adj X c d).mp hf).2 exact hnc ((hkey c d hcd).mpr h01)