AFTD Auto-Formalizing Theoretical Domains

no_sustainable_tree_fin_two

theoremverified

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$.

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

    line 3

      rintro ⟨hTree, hsus⟩
  2. 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$.

    lines 5–10

    uses is_tree_iff_is_acyclic_and_card, Nat.card_ne_zero.mp

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

    lines 13–21

    uses Iff.rfl, SimpleGraph.adj_comm

      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
  4. 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)$.

    lines 22–27

    uses Sym2.ind

      revert he hf
      induction e using Sym2.ind with
      | h a b =>
        induction f using Sym2.ind with
        | h c d =>
          intro he hf
  5. 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.

    lines 28–34

    uses SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj

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

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

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