AFTD Auto-Formalizing Theoretical Domains

not_op223_path_is_sustainable

theoremverifiedoriginal

The statement op223_path_is_sustainable is false: The statement fails at n = 2. SimpleGraph.pathGraph 2 = SimpleGraph.hasse (Fin 2) is the graph with the single edge s(0,1) on Fin 2. By is_sustainable_tree T = T.IsTree ∧ ∀ e ∈ T.edgeSet, is_sustainable_edge T e, and is_sustainable_edge T e requires the existence of a non-edge f ∈ Tᶜ.edgeSet, the unique edge of pathGraph 2 would need a non-edge; but the complement of the single edge on Fin 2 is the empty graph, so (pathGraph 2)ᶜ.edgeSet = ∅. Hence no edge of pathGraph 2 is sustainable and is_sustainable_tree (pathGraph 2) is false. (For n = 1 the condition is vacuous, so n = 2 is the only failure among n ≥ 1. The knowledge base already contains the stated lemma no_sustainable_tree_fin_two, which is exactly this obstruction.) The statement should carry the hypothesis 3 ≤ n (or n ≠ 2).

Statement

theorem not_op223_path_is_sustainable : ¬ (∀ (n : ℕ) (_hn : 1 ≤ n), is_sustainable_tree (SimpleGraph.pathGraph n))
Related work
refutes `op223_path_is_sustainable`
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_sustainable_treeA tree T is sustainable if every edge of T is 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…
  • 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

The theorem disproves the claim that every path graph is a sustainable tree by presenting the counterexample n = 2. A sustainable tree requires each of its edges to have an exchange partner in the complement graph. However, the path graph on two vertices consists of a single edge connecting its two vertices, so its complement graph has no edges at all, making edge replacement impossible.

  1. Assume for contradiction that all path graphs are sustainable trees; then the path graph on 2 vertices is a sustainable tree, so all its edges are sustainable.

    We assume the universal statement holds, instantiate it at n = 2 (where 1 ≤ 2 holds by numerical evaluation), and extract the condition that every edge of the path graph on 2 vertices is sustainable.

    lines 2–4

      intro h
      have hh : is_sustainable_tree (SimpleGraph.pathGraph 2) := h 2 (by norm_num)
      have h2 := hh.2
  2. The pair s(0, 1) is an edge of the path graph on 2 vertices.

    By definition, membership in the edge set means adjacency. Unfolding the definition of pathGraph 2 as the Hasse diagram on Fin 2 shows that 0 and 1 are adjacent.

    lines 5–7

    uses SimpleGraph.mem_edgeSet, SimpleGraph.pathGraph, SimpleGraph.hasse

      have he : s(0,1) ∈ (SimpleGraph.pathGraph 2).edgeSet := by
        rw [SimpleGraph.mem_edgeSet]
        simp [SimpleGraph.pathGraph, SimpleGraph.hasse]
  3. There exists an edge f in the complement graph of pathGraph 2.

    Because s(0, 1) is a sustainable edge, by definition of sustainability there must exist a replacement edge f in the complement graph's edge set.

    line 8

      rcases h2 (s(0,1)) he with ⟨_, f, hf, _⟩
  4. The edge set of the complement graph of pathGraph 2 is empty.

    A graph's edge set is empty precisely when the graph equals the empty graph ⊥. In the complement graph, two vertices are adjacent if and only if they are distinct and non-adjacent in pathGraph 2. By exhaustively checking all pairs in Fin 2 × Fin 2, any two distinct vertices are already adjacent in pathGraph 2, so no edge exists in the complement.

    lines 9–15

    uses SimpleGraph.edgeSet_eq_empty, SimpleGraph.compl_adj, SimpleGraph.bot_adj, iff_false, not_and, not_not, SimpleGraph.pathGraph, SimpleGraph.hasse

      have hempty : (SimpleGraph.pathGraph 2)ᶜ.edgeSet = ∅ := by
        rw [SimpleGraph.edgeSet_eq_empty]
        ext a b
        rw [SimpleGraph.compl_adj]
        simp only [SimpleGraph.bot_adj, iff_false, not_and, not_not]
        intro h
        fin_cases a <;> fin_cases b <;> simp_all [SimpleGraph.pathGraph, SimpleGraph.hasse]
  5. Contradiction: the edge f belongs to the empty set.

    Rewriting the complement's edge set with the empty set in the assumption f ∈ (pathGraph 2)ᶜ.edgeSet gives f ∈ ∅, which is a direct contradiction.

    lines 16–17

      rw [hempty] at hf
      exact hf
SimpleGraph.bot_adj
Two vertices are adjacent in the empty graph ⊥ if and only if False (i.e. it has no edges).
SimpleGraph.compl_adj
Two vertices v and w are adjacent in the complement graph Gᶜ if and only if v ≠ w and they are not adjacent in G.
SimpleGraph.edgeSet_eq_empty
The edge set of a graph G is empty if and only if G is the empty graph ⊥.
SimpleGraph.hasse
The Hasse diagram (covering relation graph) of a preorder.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of G if and only if v and w are adjacent in G.
SimpleGraph.pathGraph
The path graph on n vertices, defined as the Hasse diagram on Fin n.
iff_false
An equivalence p ↔ False is identical to ¬p.
not_and
The negation of a conjunction ¬(a ∧ b) is equivalent to a → ¬b.
not_not
Double negation elimination: ¬¬a is equivalent to a.

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

theorem not_op223_path_is_sustainable : ¬ (∀ (n : ℕ) (_hn : 1 ≤ n), is_sustainable_tree (SimpleGraph.pathGraph n)) := by  intro h  have hh : is_sustainable_tree (SimpleGraph.pathGraph 2) := h 2 (by norm_num)  have h2 := hh.2  have he : s(0,1) ∈ (SimpleGraph.pathGraph 2).edgeSet := by    rw [SimpleGraph.mem_edgeSet]    simp [SimpleGraph.pathGraph, SimpleGraph.hasse]  rcases h2 (s(0,1)) he with ⟨_, f, hf, _⟩  have hempty : (SimpleGraph.pathGraph 2)ᶜ.edgeSet = ∅ := by    rw [SimpleGraph.edgeSet_eq_empty]    ext a b    rw [SimpleGraph.compl_adj]    simp only [SimpleGraph.bot_adj, iff_false, not_and, not_not]    intro h    fin_cases a <;> fin_cases b <;> simp_all [SimpleGraph.pathGraph, SimpleGraph.hasse]  rw [hempty] at hf  exact hf
See it in the graphDiscuss this resultChallenge it