AFTD Auto-Formalizing Theoretical Domains

op223_leaf_slide_count_counterexample

theoremverifiedoriginal

There is a graph on exactly four vertices with vertices u, v and b, where u and v are distinct, b is distinct from v, v has exactly one neighbor, u-b is an edge and v-b is not, for which replacing u-b by v-b reduces the number of vertices of degree one by more than one.

Statement

theorem op223_leaf_slide_count_counterexample :
    ∃ (X : SimpleGraph (Fin 4)) (u v b : Fin 4), u ≠ v ∧ b ≠ v ∧ X.Adj u b ∧
      ¬ X.Adj v b ∧ Nat.card (X.neighborSet v) = 1 ∧
      (Finset.univ.filter (fun x : Fin 4 => Nat.card ((X.deleteEdges {s(u,b)} ⊔ SimpleGraph.fromEdgeSet {s(v,b)}).neighborSet x) = 1)).card + 1 <
        (Finset.univ.filter (fun x : Fin 4 => Nat.card (X.neighborSet x) = 1)).card
Related work
arXiv:2610.17078 Open Problem 6.1; counterexample to an auxiliary statement
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

There exist a simple graph $X$ on the vertex type Fin 4 and vertices $u, v, b : \text{Fin } 4$ such that: 1. $u \neq v$, 2. $b \neq v$, 3. $u$ and $b$ are adjacent in $X$, 4. $v$ and $b$ are not adjacent in $X$, 5. the degree of $v$ in $X$ (the cardinality of X.neighborSet v) is equal to 1, and 6. the number of vertices in $\text{Fin } 4$ with degree 1 in the graph obtained by deleting the edge $\{u, b\}$ from $X$ and adding the edge $\{v, b\}$ (i.e., X.deleteEdges {s(u,b)} ⊔ SimpleGraph.fromEdgeSet {s(v,b)}), plus 1, is strictly less than the number of vertices in $\text{Fin } 4$ with degree 1 in $X$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is established by providing an explicit counterexample: the 4-vertex path graph $P_4$ with vertices $u = 0$, $b = 1$, and $v = 3$. In $P_4$, vertices 0 and 3 are leaves (degree 1), $u$ is connected to $b$, and $v$ is not. Replacing the edge $\{0, 1\}$ with $\{3, 1\}$ isolates vertex 0 (giving it degree 0) and closes a triangle on $\{1, 2, 3\}$ (giving each of 1, 2, and 3 degree 2). This edge slide eliminates both leaves, reducing the number of degree-1 vertices from 2 to 0, which is a decrease of $2 > 1$.

  1. In the 4-vertex path graph $P_4$, vertices 0 and 3 have degree 1, while vertices 1 and 2 have degree 2.

    For each vertex in $\text{Fin } 4$, its neighbor set in the path graph $P_4$ is determined by testing adjacency via `SimpleGraph.pathGraph_adj` against all four vertices. The neighbor sets are explicitly $\{1\}$, $\{0, 2\}$, $\{1, 3\}$, and $\{2\}$, respectively. Converting each neighbor set to a finite set via `Nat.card_coe_set_eq` and `Set.ncard_coe_finset` yields cardinalities 1, 2, 2, and 1.

    lines 8–46

    uses SimpleGraph.pathGraph_adj, Nat.card_coe_set_eq, Set.ncard_coe_finset

    lemma op223_leaf_example_degree_0 : Nat.card (op223_leaf_example.neighborSet 0) = 1 := by
      have h : op223_leaf_example.neighborSet 0 = (({1} : Finset (Fin 4)) : Set (Fin 4)) := by
        ext x
        fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example, op223_leaf_example,
          SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,
          SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,
          Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide
      rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]
      norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
    
    lemma op223_leaf_example_degree_1 : Nat.card (op223_leaf_example.neighborSet 1) = 2 := by
      have h : op223_leaf_example.neighborSet 1 = (({0,2} : Finset (Fin 4)) : Set (Fin 4)) := by
        ext x
        fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example, op223_leaf_example,
          SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,
          SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,
          Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide
      rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]
      norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
    
    lemma op223_leaf_example_degree_2 : Nat.card (op223_leaf_example.neighborSet 2) = 2 := by
      have h : op223_leaf_example.neighborSet 2 = (({1,3} : Finset (Fin 4)) : Set (Fin 4)) := by
        ext x
        fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example, op223_leaf_example,
          SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,
          SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,
          Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide
      rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]
      norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
    
    lemma op223_leaf_example_degree_3 : Nat.card (op223_leaf_example.neighborSet 3) = 1 := by
      have h : op223_leaf_example.neighborSet 3 = (({2} : Finset (Fin 4)) : Set (Fin 4)) := by
        ext x
        fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example, op223_leaf_example,
          SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,
          SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,
          Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide
      rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]
      norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
  2. In the modified graph obtained by replacing edge $\{0, 1\}$ with $\{3, 1\}$, vertex 0 has degree 0, while vertices 1, 2, and 3 each have degree 2.

    The modified graph deletes the edge $\{0, 1\}$ and adds $\{3, 1\}$. Evaluating adjacencies using `SimpleGraph.deleteEdges_adj`, `SimpleGraph.fromEdgeSet_adj`, and `SimpleGraph.sup_adj` reveals that vertex 0 has no neighbors ($\emptyset$), vertex 1 has neighbors $\{2, 3\}$, vertex 2 has neighbors $\{1, 3\}$, and vertex 3 has neighbors $\{1, 2\}$. Applying `Nat.card_coe_set_eq` and `Set.ncard_coe_finset` shows that vertex 0 has degree 0 and vertices 1, 2, 3 all have degree 2.

    lines 48–86

    uses SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.sup_adj, Nat.card_coe_set_eq, Set.ncard_coe_finset

    lemma op223_leaf_example_after_degree_0 : Nat.card (op223_leaf_example_after.neighborSet 0) = 0 := by
      have h : op223_leaf_example_after.neighborSet 0 = ((∅ : Finset (Fin 4)) : Set (Fin 4)) := by
        ext x
        fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example_after, op223_leaf_example,
          SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,
          SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,
          Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide
      rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]
      norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
    
    lemma op223_leaf_example_after_degree_1 : Nat.card (op223_leaf_example_after.neighborSet 1) = 2 := by
      have h : op223_leaf_example_after.neighborSet 1 = (({2,3} : Finset (Fin 4)) : Set (Fin 4)) := by
        ext x
        fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example_after, op223_leaf_example,
          SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,
          SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,
          Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide
      rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]
      norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
    
    lemma op223_leaf_example_after_degree_2 : Nat.card (op223_leaf_example_after.neighborSet 2) = 2 := by
      have h : op223_leaf_example_after.neighborSet 2 = (({1,3} : Finset (Fin 4)) : Set (Fin 4)) := by
        ext x
        fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example_after, op223_leaf_example,
          SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,
          SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,
          Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide
      rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]
      norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
    
    lemma op223_leaf_example_after_degree_3 : Nat.card (op223_leaf_example_after.neighborSet 3) = 2 := by
      have h : op223_leaf_example_after.neighborSet 3 = (({1,2} : Finset (Fin 4)) : Set (Fin 4)) := by
        ext x
        fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example_after, op223_leaf_example,
          SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,
          SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,
          Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide
      rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]
      norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
  3. The path graph $P_4$ with vertices $u = 0, v = 3, b = 1$ satisfies all initial hypotheses: $u \ne v$, $b \ne v$, $u$ is adjacent to $b$, $v$ is not adjacent to $b$, and $v$ has degree 1.

    We instantiate the existential quantifier with graph $X = P_4$ and vertices $u = 0$, $v = 3$, and $b = 1$. The inequalities $0 \ne 3$ and $1 \ne 3$ hold trivially. Adjacency of 0 and 1 in $P_4$ and non-adjacency of 3 and 1 follow from `SimpleGraph.pathGraph_adj` since $|0 - 1| = 1$ but $|3 - 1| \ne 1$. Vertex 3 has degree 1 by `op223_leaf_example_degree_3`.

    lines 88–95

    uses SimpleGraph.pathGraph_adj, op223_leaf_example_degree_3

    theorem op223_leaf_slide_count_counterexample :
        ∃ (X : SimpleGraph (Fin 4)) (u v b : Fin 4), u ≠ v ∧ b ≠ v ∧ X.Adj u b ∧
          ¬ X.Adj v b ∧ Nat.card (X.neighborSet v) = 1 ∧
          (Finset.univ.filter (fun x : Fin 4 => Nat.card ((X.deleteEdges {s(u,b)} ⊔ SimpleGraph.fromEdgeSet {s(v,b)}).neighborSet x) = 1)).card + 1 <
            (Finset.univ.filter (fun x : Fin 4 => Nat.card (X.neighborSet x) = 1)).card := by
      refine ⟨op223_leaf_example, 0, 3, 1, by decide, by decide, ?_, ?_, op223_leaf_example_degree_3, ?_⟩
      · norm_num [op223_leaf_example, SimpleGraph.pathGraph_adj]
      · norm_num [op223_leaf_example, SimpleGraph.pathGraph_adj]
  4. The modified graph contains no vertices of degree 1.

    We rephrase the remaining inequality in terms of the modified graph `op223_leaf_example_after` and show that the set of degree-1 vertices is empty. By exhaustive case analysis on all vertices $x \in \text{Fin } 4$, the previously computed degrees from `op223_leaf_example_after_degree_0` through `op223_leaf_example_after_degree_3` are 0, 2, 2, and 2; since none of these equals 1, no vertex is a leaf.

    lines 96–109

    uses op223_leaf_example_after_degree_0, op223_leaf_example_after_degree_1, op223_leaf_example_after_degree_2, op223_leaf_example_after_degree_3

      · change (Finset.univ.filter (fun x : Fin 4 => Nat.card (op223_leaf_example_after.neighborSet x) = 1)).card + 1 <
          (Finset.univ.filter (fun x : Fin 4 => Nat.card (op223_leaf_example.neighborSet x) = 1)).card
        have ha : Finset.univ.filter (fun x : Fin 4 => Nat.card (op223_leaf_example_after.neighborSet x) = 1) = ∅ := by
          ext x
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty, iff_false]
          fin_cases x
          · change ¬ Nat.card (op223_leaf_example_after.neighborSet 0) = 1
            rw [op223_leaf_example_after_degree_0]; decide
          · change ¬ Nat.card (op223_leaf_example_after.neighborSet 1) = 1
            rw [op223_leaf_example_after_degree_1]; decide
          · change ¬ Nat.card (op223_leaf_example_after.neighborSet 2) = 1
            rw [op223_leaf_example_after_degree_2]; decide
          · change ¬ Nat.card (op223_leaf_example_after.neighborSet 3) = 1
            rw [op223_leaf_example_after_degree_3]; decide
  5. The path graph $P_4$ contains exactly two vertices of degree 1, namely 0 and 3.

    We determine the set of leaves in $P_4$. Testing each vertex $x \in \text{Fin } 4$ with the degree lemmas `op223_leaf_example_degree_0` through `op223_leaf_example_degree_3` shows that $\deg(x) = 1$ holds if and only if $x = 0$ or $x = 3$. Hence, the set of degree-1 vertices is precisely $\{0, 3\}$.

    lines 110–121

    uses op223_leaf_example_degree_0, op223_leaf_example_degree_1, op223_leaf_example_degree_2, op223_leaf_example_degree_3

        have hb : Finset.univ.filter (fun x : Fin 4 => Nat.card (op223_leaf_example.neighborSet x) = 1) = {0,3} := by
          ext x
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton]
          fin_cases x
          · change (Nat.card (op223_leaf_example.neighborSet 0) = 1) ↔ ((0 : Fin 4) = 0 ∨ (0 : Fin 4) = 3)
            rw [op223_leaf_example_degree_0]; decide
          · change (Nat.card (op223_leaf_example.neighborSet 1) = 1) ↔ ((1 : Fin 4) = 0 ∨ (1 : Fin 4) = 3)
            rw [op223_leaf_example_degree_1]; decide
          · change (Nat.card (op223_leaf_example.neighborSet 2) = 1) ↔ ((2 : Fin 4) = 0 ∨ (2 : Fin 4) = 3)
            rw [op223_leaf_example_degree_2]; decide
          · change (Nat.card (op223_leaf_example.neighborSet 3) = 1) ↔ ((3 : Fin 4) = 0 ∨ (3 : Fin 4) = 3)
            rw [op223_leaf_example_degree_3]; decide
  6. The number of degree-1 vertices decreases from 2 to 0, which is a reduction of more than 1.

    Substituting the empty leaf set for the modified graph and $\{0, 3\}$ for the original graph reduces the required inequality to $|\emptyset| + 1 < |\{0, 3\}|$. By evaluation of finite set cardinalities via `Finset.card_insert_eq_ite` and `Fin.ext_iff`, this simplifies to $0 + 1 < 2$, which holds.

    lines 122–123

    uses Finset.card_insert_eq_ite, Fin.ext_iff

        rw [ha,hb]
        norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
Fin.ext_iff
Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
Finset.card_insert_eq_ite
Inserting an element into a finite set increases its cardinality by 1 if the element is not already in the set, and leaves the cardinality unchanged if it is.
Nat.card_coe_set_eq
The cardinality `Nat.card` of a coerced set equals its set cardinality `ncard`.
op223_leaf_example_after_degree_0
In the graph obtained by removing the edge between 0 and 1 from $P_4$ and adding the edge between 3 and 1, vertex 0 has degree 0.
op223_leaf_example_after_degree_1
In the graph obtained by removing the edge between 0 and 1 from $P_4$ and adding the edge between 3 and 1, vertex 1 has degree 2.
op223_leaf_example_after_degree_2
In the graph obtained by removing the edge between 0 and 1 from $P_4$ and adding the edge between 3 and 1, vertex 2 has degree 2.
op223_leaf_example_after_degree_3
In the graph obtained by removing the edge between 0 and 1 from $P_4$ and adding the edge between 3 and 1, vertex 3 has degree 2.
op223_leaf_example_degree_0
In the 4-vertex path graph, vertex 0 has degree 1.
op223_leaf_example_degree_1
In the 4-vertex path graph, vertex 1 has degree 2.
op223_leaf_example_degree_2
In the 4-vertex path graph, vertex 2 has degree 2.
op223_leaf_example_degree_3
In the 4-vertex path graph, vertex 3 has degree 1.
Set.ncard_coe_finset
The set cardinality `ncard` of a coerced finite set equals its finite set cardinality `card`.
SimpleGraph.deleteEdges_adj
Two vertices are adjacent in a graph with deleted edges if and only if they were adjacent in the original graph and the edge between them is not in the set of deleted edges.
SimpleGraph.fromEdgeSet_adj
Two distinct vertices are adjacent in a graph constructed from an edge set if and only if the edge connecting them belongs to that edge set.
SimpleGraph.pathGraph_adj
In the path graph on $n$ vertices, two vertices are adjacent if and only if their indices differ by 1.
SimpleGraph.sup_adj
Two vertices are adjacent in the union of two graphs if and only if they are adjacent in at least one of the two graphs.

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 SimpleGraphopen scoped Classicaldef op223_leaf_example : SimpleGraph (Fin 4) := SimpleGraph.pathGraph 4def op223_leaf_example_after : SimpleGraph (Fin 4) :=  op223_leaf_example.deleteEdges {s(0,1)} ⊔ SimpleGraph.fromEdgeSet {s(3,1)}lemma op223_leaf_example_degree_0 : Nat.card (op223_leaf_example.neighborSet 0) = 1 := by  have h : op223_leaf_example.neighborSet 0 = (({1} : Finset (Fin 4)) : Set (Fin 4)) := by    ext x    fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example, op223_leaf_example,      SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,      SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,      Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide  rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]  norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]lemma op223_leaf_example_degree_1 : Nat.card (op223_leaf_example.neighborSet 1) = 2 := by  have h : op223_leaf_example.neighborSet 1 = (({0,2} : Finset (Fin 4)) : Set (Fin 4)) := by    ext x    fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example, op223_leaf_example,      SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,      SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,      Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide  rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]  norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]lemma op223_leaf_example_degree_2 : Nat.card (op223_leaf_example.neighborSet 2) = 2 := by  have h : op223_leaf_example.neighborSet 2 = (({1,3} : Finset (Fin 4)) : Set (Fin 4)) := by    ext x    fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example, op223_leaf_example,      SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,      SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,      Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide  rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]  norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]lemma op223_leaf_example_degree_3 : Nat.card (op223_leaf_example.neighborSet 3) = 1 := by  have h : op223_leaf_example.neighborSet 3 = (({2} : Finset (Fin 4)) : Set (Fin 4)) := by    ext x    fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example, op223_leaf_example,      SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,      SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,      Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide  rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]  norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]lemma op223_leaf_example_after_degree_0 : Nat.card (op223_leaf_example_after.neighborSet 0) = 0 := by  have h : op223_leaf_example_after.neighborSet 0 = ((∅ : Finset (Fin 4)) : Set (Fin 4)) := by    ext x    fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example_after, op223_leaf_example,      SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,      SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,      Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide  rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]  norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]lemma op223_leaf_example_after_degree_1 : Nat.card (op223_leaf_example_after.neighborSet 1) = 2 := by  have h : op223_leaf_example_after.neighborSet 1 = (({2,3} : Finset (Fin 4)) : Set (Fin 4)) := by    ext x    fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example_after, op223_leaf_example,      SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,      SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,      Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide  rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]  norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]lemma op223_leaf_example_after_degree_2 : Nat.card (op223_leaf_example_after.neighborSet 2) = 2 := by  have h : op223_leaf_example_after.neighborSet 2 = (({1,3} : Finset (Fin 4)) : Set (Fin 4)) := by    ext x    fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example_after, op223_leaf_example,      SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,      SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,      Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide  rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]  norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]lemma op223_leaf_example_after_degree_3 : Nat.card (op223_leaf_example_after.neighborSet 3) = 2 := by  have h : op223_leaf_example_after.neighborSet 3 = (({1,2} : Finset (Fin 4)) : Set (Fin 4)) := by    ext x    fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, op223_leaf_example_after, op223_leaf_example,      SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj,      SimpleGraph.pathGraph_adj, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe,      Finset.mem_insert, Finset.mem_singleton, Finset.notMem_empty] <;> decide  rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset]  norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]theorem op223_leaf_slide_count_counterexample :    ∃ (X : SimpleGraph (Fin 4)) (u v b : Fin 4), u ≠ v ∧ b ≠ v ∧ X.Adj u b ∧      ¬ X.Adj v b ∧ Nat.card (X.neighborSet v) = 1 ∧      (Finset.univ.filter (fun x : Fin 4 => Nat.card ((X.deleteEdges {s(u,b)} ⊔ SimpleGraph.fromEdgeSet {s(v,b)}).neighborSet x) = 1)).card + 1 <        (Finset.univ.filter (fun x : Fin 4 => Nat.card (X.neighborSet x) = 1)).card := by  refine ⟨op223_leaf_example, 0, 3, 1, by decide, by decide, ?_, ?_, op223_leaf_example_degree_3, ?_⟩  · norm_num [op223_leaf_example, SimpleGraph.pathGraph_adj]  · norm_num [op223_leaf_example, SimpleGraph.pathGraph_adj]  · change (Finset.univ.filter (fun x : Fin 4 => Nat.card (op223_leaf_example_after.neighborSet x) = 1)).card + 1 <      (Finset.univ.filter (fun x : Fin 4 => Nat.card (op223_leaf_example.neighborSet x) = 1)).card    have ha : Finset.univ.filter (fun x : Fin 4 => Nat.card (op223_leaf_example_after.neighborSet x) = 1) = ∅ := by      ext x      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty, iff_false]      fin_cases x      · change ¬ Nat.card (op223_leaf_example_after.neighborSet 0) = 1        rw [op223_leaf_example_after_degree_0]; decide      · change ¬ Nat.card (op223_leaf_example_after.neighborSet 1) = 1        rw [op223_leaf_example_after_degree_1]; decide      · change ¬ Nat.card (op223_leaf_example_after.neighborSet 2) = 1        rw [op223_leaf_example_after_degree_2]; decide      · change ¬ Nat.card (op223_leaf_example_after.neighborSet 3) = 1        rw [op223_leaf_example_after_degree_3]; decide    have hb : Finset.univ.filter (fun x : Fin 4 => Nat.card (op223_leaf_example.neighborSet x) = 1) = {0,3} := by      ext x      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton]      fin_cases x      · change (Nat.card (op223_leaf_example.neighborSet 0) = 1) ↔ ((0 : Fin 4) = 0 ∨ (0 : Fin 4) = 3)        rw [op223_leaf_example_degree_0]; decide      · change (Nat.card (op223_leaf_example.neighborSet 1) = 1) ↔ ((1 : Fin 4) = 0 ∨ (1 : Fin 4) = 3)        rw [op223_leaf_example_degree_1]; decide      · change (Nat.card (op223_leaf_example.neighborSet 2) = 1) ↔ ((2 : Fin 4) = 0 ∨ (2 : Fin 4) = 3)        rw [op223_leaf_example_degree_2]; decide      · change (Nat.card (op223_leaf_example.neighborSet 3) = 1) ↔ ((3 : Fin 4) = 0 ∨ (3 : Fin 4) = 3)        rw [op223_leaf_example_degree_3]; decide    rw [ha,hb]    norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
See it in the graphDiscuss this resultChallenge it