op223_leaf_slide_count_counterexample
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$.
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.
uses
SimpleGraph.pathGraph_adj,Nat.card_coe_set_eq,Set.ncard_coe_finsetlemma 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]
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.
uses
SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,SimpleGraph.sup_adj,Nat.card_coe_set_eq,Set.ncard_coe_finsetlemma 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]
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`.
uses
SimpleGraph.pathGraph_adj,op223_leaf_example_degree_3theorem 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]
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.
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
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\}$.
uses
op223_leaf_example_degree_0,op223_leaf_example_degree_1,op223_leaf_example_degree_2,op223_leaf_example_degree_3have 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
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.
uses
Finset.card_insert_eq_ite,Fin.ext_iffrw [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.
- The neighbor sets and vertex degrees are verified by exhaustive case analysis over the four elements of the finite type `Fin 4` using `fin_cases` and `decide`.
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.
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]