not_op223_path_is_sustainable
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.
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.
intro h have hh : is_sustainable_tree (SimpleGraph.pathGraph 2) := h 2 (by norm_num) have h2 := hh.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.
uses
SimpleGraph.mem_edgeSet,SimpleGraph.pathGraph,SimpleGraph.hassehave he : s(0,1) ∈ (SimpleGraph.pathGraph 2).edgeSet := by rw [SimpleGraph.mem_edgeSet] simp [SimpleGraph.pathGraph, SimpleGraph.hasse]
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.
rcases h2 (s(0,1)) he with ⟨_, f, hf, _⟩
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.
uses
SimpleGraph.edgeSet_eq_empty,SimpleGraph.compl_adj,SimpleGraph.bot_adj,iff_false,not_and,not_not,SimpleGraph.pathGraph,SimpleGraph.hassehave 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]
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.
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.
- The case exhaustion on Fin 2 in line 15 checks all four pairs (a, b) ∈ Fin 2 × Fin 2; the diagonal cases a = b contradict the hypothesis a ≠ b, and the off-diagonal cases are verified by unfolding the path graph definition.
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.
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