AFTD Auto-Formalizing Theoretical Domains

op223_nonsustainable_has_bad_edge

theoremverified

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

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.

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

    lines 6–9

      classical
      have hbad : ¬ ∀ e ∈ T.edgeSet, is_sustainable_edge T e := by
        intro h
        exact hT.2 ⟨hT.1, h⟩
  2. 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.

    lines 10–11

      push_neg at hbad
      obtain ⟨e, he, hnot⟩ := hbad
  3. 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.

    lines 12–13

    uses Sym2.ind

      induction 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 : α.

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_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⟩
See it in the graphDiscuss this resultChallenge it