op223_conditional_slide_refutation
If the example graph is sustainable and its two possible slides at the edge 4-5 are nonsustainable, then the universal leaf-slide predecessor assertion is false.
Statement
theorem op223_conditional_slide_refutation
(hX : is_sustainable_tree op223_example_graph)
(h0 : ¬ is_sustainable_tree (op223_example_slide 0))
(h6 : ¬ is_sustainable_tree (op223_example_slide 6)) :
¬ (∀ (n : ℕ) (X : SimpleGraph (Fin n)), is_sustainable_tree X →
∀ (u v : Fin n) (p : X.Walk u v), u ≠ v → p.IsPath →
(∀ x ∈ p.support, x ≠ u → x ≠ v → Nat.card (X.neighborSet x) = 2) →
3 ≤ Nat.card (X.neighborSet u) → Nat.card (X.neighborSet v) = 1 →
∃ b : Fin n, X.Adj u b ∧ ¬ X.Adj v b ∧ b ∉ p.support ∧
is_sustainable_tree (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)}))- Source
- arXiv:2610.17078 Open Problem 6.1; exact experiment 22883
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- op223_example_graphThe eight-vertex tree with edges 01, 04, 07, 12, 23, 45 and 46.
- op223_example_slideReplace edge 4-b by 5-b in the eight-vertex example.
- is_sustainable_treeA tree T is sustainable if every edge of T is sustainable.
The proof, explained
The theorem is proved by contradiction: assuming the universal leaf-slide predecessor assertion holds, it is instantiated with an 8-vertex example graph, endpoints u = 4 and v = 5, and the single-edge path between them. In this graph, vertex 4 has degree 3 with neighbors {0, 5, 6}, vertex 5 is a leaf with unique neighbor 4, and there are no internal vertices on the path. The assertion implies that one of the neighbors of 4 (other than 5) can slide to 5 to yield a sustainable tree. However, this leaves only 0 and 6 as candidates, and both slides are assumed to be nonsustainable, deriving a contradiction.
Assume for contradiction that the universal leaf-slide predecessor assertion holds.
We introduce the negated statement as hypothesis h, which asserts that for any sustainable tree, any path from a vertex u of degree at least 3 to a leaf v with all internal vertices of degree 2 admits a neighbor b of u that can slide to v while preserving sustainability.
intro hVertices 4 and 5 are adjacent in the example graph, and the single edge between them defines a valid path p from 4 to 5.
Unfolding the definition of op223_example_graph shows that (4, 5) is an edge. We form the walk p consisting of this single edge; because the trivial walk at 5 only visits 5, vertex 4 is not in its support, so SimpleGraph.Walk.IsPath.cons verifies that p is a path.
uses
SimpleGraph.fromEdgeSet_adj,Sym2.eq,SimpleGraph.Walk.IsPath.cons,SimpleGraph.Walk.IsPath.nilhave h45 : op223_example_graph.Adj 4 5 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] let p : op223_example_graph.Walk 4 5 := .cons h45 .nil have hp : p.IsPath := by apply SimpleGraph.Walk.IsPath.cons SimpleGraph.Walk.IsPath.nil simp
Every internal vertex along the path p has degree 2.
The vertex support of p consists only of 4 and 5. There are no vertices on the path distinct from both endpoints, so the degree condition on internal vertices holds vacuously.
have hint : ∀ x ∈ p.support, x ≠ 4 → x ≠ 5 → Nat.card (op223_example_graph.neighborSet x) = 2 := by intro x hx hx4 hx5 simp [p] at hx rcases hx with rfl | rfl <;> contradiction
The neighbor set of vertex 4 is {0, 5, 6}, so vertex 4 has degree at least 3.
Exhaustive case analysis across all 8 vertices of the graph shows that exactly 0, 5, and 6 are adjacent to 4. Converting from set cardinality to finset cardinality evaluates the degree of 4 to 3, which satisfies the requirement deg(4) ≥ 3.
uses
SimpleGraph.fromEdgeSet_adj,Sym2.eq,Nat.card_coe_set_eq,Set.ncard_coe_finsethave ht : op223_example_graph.neighborSet 4 = (({0, 5, 6} : Finset (Fin 8)) : Set (Fin 8)) := by ext x; fin_cases x <;> simp [SimpleGraph.neighborSet, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have hu : 3 ≤ Nat.card (op223_example_graph.neighborSet 4) := by rw [Nat.card_coe_set_eq, ht, Set.ncard_coe_finset] decide
The neighbor set of vertex 5 is {4}, so vertex 5 has degree 1.
Similarly, checking all 8 vertices confirms that 4 is the unique neighbor of 5. Evaluating the cardinality shows that vertex 5 has degree 1, verifying that it is a leaf.
uses
SimpleGraph.fromEdgeSet_adj,Sym2.eq,Nat.card_coe_set_eq,Set.ncard_coe_finsethave hv : Nat.card (op223_example_graph.neighborSet 5) = 1 := by have ht : op223_example_graph.neighborSet 5 = (({4} : Finset (Fin 8)) : Set (Fin 8)) := by ext x; fin_cases x <;> simp [SimpleGraph.neighborSet, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] rw [Nat.card_coe_set_eq, ht, Set.ncard_coe_finset] decide
The universal assumption h guarantees a neighbor b of 4 whose slide to 5 yields a sustainable tree.
We instantiate the universal hypothesis h with n = 8, the example graph, the hypothesis hX that it is sustainable, vertices u = 4 and v = 5, and the path p. Because all prerequisites (u ≠ v, p is a path, internal degrees are 2, deg(4) ≥ 3, deg(5) = 1) have been established, h produces a neighbor b of 4 with b ∉ p.support such that sliding the edge (4, b) to (5, b) produces a sustainable tree.
obtain ⟨b, hb, hn, hnot, hs⟩ := h 8 op223_example_graph hX 4 5 p (by decide) hp hint hu hv
The candidate neighbor b must be 0, 5, or 6.
Since b is adjacent to 4, it belongs to the neighbor set of 4, which was shown to be {0, 5, 6}.
have hb' : b = 0 ∨ b = 5 ∨ b = 6 := by have hm : b ∈ op223_example_graph.neighborSet 4 := hb rw [ht] at hm simpa using hm
Each possible value of b leads to a contradiction, refuting the universal assertion.
If b = 0, the resulting graph is op223_example_slide 0, which would be sustainable, contradicting hypothesis h0. If b = 5, then b is in the support {4, 5} of p, contradicting the requirement that b ∉ p.support. If b = 6, the resulting graph is op223_example_slide 6, which would be sustainable, contradicting hypothesis h6. Having eliminated all possibilities, the universal assertion is refuted.
rcases hb' with rfl | rfl | rfl · exact h0 hs · exact hnot (by simp [p]) · exact h6 hs
SimpleGraph.fromEdgeSet_adj- In a simple graph constructed from a set of unordered pairs, two vertices are adjacent if and only if the unordered pair is in the edge set and the two vertices are distinct.
Sym2.eq- Two unordered pairs s(a, b) and s(c, d) are equal if and only if either (a = c and b = d) or (a = d and b = c).
SimpleGraph.Walk.IsPath.cons- Prepending an edge (u, v) to a path p produces a new path, provided that u does not already appear in the vertex support of p.
SimpleGraph.Walk.IsPath.nil- The trivial walk consisting of a single vertex and no edges is a path.
Nat.card_coe_set_eq- The cardinality of a set coerced to a type (Nat.card) equals the cardinality of the set itself (s.ncard).
Set.ncard_coe_finset- The set cardinality (s.ncard) of a Finset coerced to a set equals its Finset cardinality (s.card).
- The sustainability of the example graph and the nonsustainability of its slides at 0 and 6 are provided as external hypotheses (hX, h0, h6) to this theorem rather than computed directly within it.
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 op223_conditional_slide_refutation (hX : is_sustainable_tree op223_example_graph) (h0 : ¬ is_sustainable_tree (op223_example_slide 0)) (h6 : ¬ is_sustainable_tree (op223_example_slide 6)) : ¬ (∀ (n : ℕ) (X : SimpleGraph (Fin n)), is_sustainable_tree X → ∀ (u v : Fin n) (p : X.Walk u v), u ≠ v → p.IsPath → (∀ x ∈ p.support, x ≠ u → x ≠ v → Nat.card (X.neighborSet x) = 2) → 3 ≤ Nat.card (X.neighborSet u) → Nat.card (X.neighborSet v) = 1 → ∃ b : Fin n, X.Adj u b ∧ ¬ X.Adj v b ∧ b ∉ p.support ∧ is_sustainable_tree (X.deleteEdges {s(u, b)} ⊔ SimpleGraph.fromEdgeSet {s(v, b)})) := by intro h have h45 : op223_example_graph.Adj 4 5 := by simp [op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] let p : op223_example_graph.Walk 4 5 := .cons h45 .nil have hp : p.IsPath := by apply SimpleGraph.Walk.IsPath.cons SimpleGraph.Walk.IsPath.nil simp have hint : ∀ x ∈ p.support, x ≠ 4 → x ≠ 5 → Nat.card (op223_example_graph.neighborSet x) = 2 := by intro x hx hx4 hx5 simp [p] at hx rcases hx with rfl | rfl <;> contradiction have ht : op223_example_graph.neighborSet 4 = (({0, 5, 6} : Finset (Fin 8)) : Set (Fin 8)) := by ext x; fin_cases x <;> simp [SimpleGraph.neighborSet, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] have hu : 3 ≤ Nat.card (op223_example_graph.neighborSet 4) := by rw [Nat.card_coe_set_eq, ht, Set.ncard_coe_finset] decide have hv : Nat.card (op223_example_graph.neighborSet 5) = 1 := by have ht : op223_example_graph.neighborSet 5 = (({4} : Finset (Fin 8)) : Set (Fin 8)) := by ext x; fin_cases x <;> simp [SimpleGraph.neighborSet, op223_example_graph, SimpleGraph.fromEdgeSet_adj, Sym2.eq] rw [Nat.card_coe_set_eq, ht, Set.ncard_coe_finset] decide obtain ⟨b, hb, hn, hnot, hs⟩ := h 8 op223_example_graph hX 4 5 p (by decide) hp hint hu hv have hb' : b = 0 ∨ b = 5 ∨ b = 6 := by have hm : b ∈ op223_example_graph.neighborSet 4 := hb rw [ht] at hm simpa using hm rcases hb' with rfl | rfl | rfl · exact h0 hs · exact hnot (by simp [p]) · exact h6 hs