AFTD Auto-Formalizing Theoretical Domains

op223_conditional_slide_refutation

theoremverified

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

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.

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

    line 11

      intro h
  2. Vertices 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.

    lines 12–17

    uses SimpleGraph.fromEdgeSet_adj, Sym2.eq, SimpleGraph.Walk.IsPath.cons, SimpleGraph.Walk.IsPath.nil

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

    lines 18–22

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

    lines 23–27

    uses SimpleGraph.fromEdgeSet_adj, Sym2.eq, Nat.card_coe_set_eq, Set.ncard_coe_finset

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

    lines 28–32

    uses SimpleGraph.fromEdgeSet_adj, Sym2.eq, Nat.card_coe_set_eq, Set.ncard_coe_finset

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

    line 33

      obtain ⟨b, hb, hn, hnot, hs⟩ := h 8 op223_example_graph hX 4 5 p (by decide) hp hint hu hv
  7. 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}.

    lines 34–37

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

    lines 38–41

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

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