op223_nonleaf_count_counterexample
There is a graph on three vertices with adjacent u and v of degree at least two for which the adjacent shift reduces the number of vertices of degree greater than one by more than one.
Statement
theorem op223_nonleaf_count_counterexample : ∃ (T : SimpleGraph (Fin 3)) (u v : Fin 3), T.Adj u v ∧ 2 ≤ Nat.card (T.neighborSet u) ∧ 2 ≤ Nat.card (T.neighborSet v) ∧ (Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card ((gts_graph T u v u).neighborSet x))).card + 1 < (Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (T.neighborSet x))).card
- Related work
- arXiv:2610.17078 Open Problem 6.1; counterexample to an auxiliary statement
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- gts_graphThe graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between…
Read back from the Lean
There exist a simple graph $T$ on the vertex set Fin 3 and vertices $u, v \in \text{Fin } 3$ such that:
1. $u$ and $v$ are adjacent in $T$;
2. the degree of $u$ in $T$ (the cardinality of its neighbor set) is at least 2;
3. the degree of $v$ in $T$ is at least 2; and
4. the number of vertices in Fin 3 having degree strictly greater than 1 in gts_graph T u v u, plus 1, is strictly less than the number of vertices in Fin 3 having degree strictly greater than 1 in $T$ (i.e., the number of vertices of degree $> 1$ decreases by at least 2 after the operation).
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 proved by providing an explicit counterexample: the triangle graph K₃ on vertices {0, 1, 2} with adjacent vertices u = 0 and v = 1. In K₃, all 3 vertices have degree 2, so the set of vertices of degree greater than one has cardinality 3. The adjacent shift of v = 1 to u = 0 replaces the edge {1, 2} with {0, 2}, resulting in a star graph with edges {0, 1} and {0, 2}. In this shifted graph, vertex 0 retains degree 2 while vertices 1 and 2 become leaves of degree 1, leaving only 1 vertex of degree greater than one. Since 1 + 1 < 3, the number of non-leaf vertices has decreased by 2, which is strictly more than one.
The shifted graph op223_triangle_shift consists of exactly two edges: {0, 1} and {0, 2}. automation
By graph extensionality (`ext a b`), two graphs are identical if they share the same adjacency relation. We exhaust all 9 pairs of vertices in Fin 3 using `fin_cases`. For each pair, unfolding the GTS shift definition and simplifying edge membership shows that a and b are adjacent in the shifted graph if and only if the edge between them is {0, 1} or {0, 2}.
uses
SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,SimpleGraph.top_adj,Sym2.eq,Fin.exists_fin_succext a b fin_cases a <;> fin_cases b <;> simp only [op223_triangle_shift, op223_triangle, gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Set.mem_setOf_eq, Set.mem_insert_iff, Set.mem_singleton_iff, SimpleGraph.top_adj, Sym2.eq, Fin.exists_fin_succ] <;> decide
In the triangle graph K₃, the neighbor set of any vertex x consists of all vertices other than x.
By extensionality, a vertex y is adjacent to x in the complete graph ⊤ if and only if y ≠ x, which means y is in the universal set minus {x}.
uses
SimpleGraph.neighborSet,SimpleGraph.top_adj,ne_commext y simp [op223_triangle, SimpleGraph.neighborSet, SimpleGraph.top_adj, ne_comm]
In the triangle graph K₃, every vertex has degree 2.
The degree of x is the cardinality of its neighbor set. Since the neighbor set is univ \ {x} by `op223_triangle_neighbors`, its cardinality is 3 - 1 = 2.
uses
Nat.card_coe_set_eq,op223_triangle_neighbors,Set.ncard_coe_finsetrw [Nat.card_coe_set_eq, op223_triangle_neighbors, Set.ncard_coe_finset] simp
In the shifted graph, vertex 0 has degree 2.
Using the explicit edge set from `op223_triangle_shift_graph`, checking every vertex shows that the neighbor set of vertex 0 is precisely {1, 2}. Computing the cardinality of this two-element set yields 2.
uses
op223_triangle_shift_graph,SimpleGraph.mem_neighborSet,SimpleGraph.fromEdgeSet_adj,Nat.card_coe_set_eq,Set.ncard_coe_finset,Finset.card_insert_eq_ite,Fin.ext_iffhave h : op223_triangle_shift.neighborSet 0 = (({1,2} : Finset (Fin 3)) : Set (Fin 3)) := by rw [op223_triangle_shift_graph] ext x; fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_insert_iff, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] <;> decide rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset] norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]
In the shifted graph, vertex 1 has degree 1.
Checking against `op223_triangle_shift_graph` reveals that the only neighbor of vertex 1 is vertex 0. Its neighbor set is therefore {0}, which has cardinality 1.
uses
op223_triangle_shift_graph,SimpleGraph.mem_neighborSet,SimpleGraph.fromEdgeSet_adj,Nat.card_coe_set_eq,Set.ncard_coe_finsethave h : op223_triangle_shift.neighborSet 1 = (({0} : Finset (Fin 3)) : Set (Fin 3)) := by rw [op223_triangle_shift_graph] ext x; fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_insert_iff, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] <;> decide rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset] norm_num
In the shifted graph, vertex 2 has degree 1.
Similarly, testing against the edge set shows that the neighbor set of vertex 2 is {0}, giving it degree 1.
uses
op223_triangle_shift_graph,SimpleGraph.mem_neighborSet,SimpleGraph.fromEdgeSet_adj,Nat.card_coe_set_eq,Set.ncard_coe_finsethave h : op223_triangle_shift.neighborSet 2 = (({0} : Finset (Fin 3)) : Set (Fin 3)) := by rw [op223_triangle_shift_graph] ext x; fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_insert_iff, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] <;> decide rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset] norm_num
The triangle graph K₃ with vertices u = 0 and v = 1 satisfies the adjacency and minimum degree conditions: 0 is adjacent to 1, and both have degree at least 2.
We instantiate the existential witness with T = K₃, u = 0, and v = 1. Vertices 0 and 1 are distinct and therefore adjacent in K₃. By `op223_triangle_degree`, every vertex in K₃ has degree 2, so deg(0) ≥ 2 and deg(1) ≥ 2 hold immediately.
uses
op223_triangle_degreerefine ⟨op223_triangle, 0, 1, ?_, ?_, ?_, ?_⟩ · simp [op223_triangle] · rw [op223_triangle_degree] · rw [op223_triangle_degree]
In the shifted graph, the only vertex of degree strictly greater than 1 is vertex 0.
We unfold the shifted graph definition and evaluate the predicate 1 < deg(x) for each x ∈ Fin 3 using `fin_cases`. By the earlier degree calculations, deg(0) = 2 > 1, while deg(1) = 1 and deg(2) = 1. Thus the filtered set of vertices of degree greater than 1 is the singleton {0}.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_singleton,op223_triangle_shift_degree_zero,op223_triangle_shift_degree_one,op223_triangle_shift_degree_two· change (Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (op223_triangle_shift.neighborSet x))).card + 1 < (Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (op223_triangle.neighborSet x))).card have hf : Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (op223_triangle_shift.neighborSet x)) = {0} := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton] fin_cases x · change (1 < Nat.card (op223_triangle_shift.neighborSet 0)) ↔ (0 : Fin 3) = 0 rw [op223_triangle_shift_degree_zero]; decide · change (1 < Nat.card (op223_triangle_shift.neighborSet 1)) ↔ (1 : Fin 3) = 0 rw [op223_triangle_shift_degree_one]; decide · change (1 < Nat.card (op223_triangle_shift.neighborSet 2)) ↔ (2 : Fin 3) = 0 rw [op223_triangle_shift_degree_two]; decide
In the triangle graph K₃, every vertex has degree strictly greater than 1, so the filtered set is all of Finset.univ.
Since every vertex x in K₃ has degree 2 by `op223_triangle_degree`, the condition 1 < deg(x) holds universally. Filtering the universe by a predicate that holds everywhere leaves the whole set Finset.univ.
uses
Finset.filter_true_of_mem,op223_triangle_degreehave hg : Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (op223_triangle.neighborSet x)) = Finset.univ := by apply Finset.filter_true_of_mem intro x hx rw [op223_triangle_degree] decide
The number of vertices of degree greater than 1 in the shifted graph plus 1 is strictly less than in the original triangle graph.
Rewriting with the evaluations of both filtered sets yields |{0}| + 1 < |Finset.univ|, which simplifies to 1 + 1 < 3 (that is, 2 < 3). This completes the proof of the counterexample.
rw [hf, hg] simp
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 graphs.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent after deleting a set of edges if and only if they were adjacent originally and the edge between them was not deleted.
SimpleGraph.fromEdgeSet_adj- Two vertices are adjacent in a graph defined from an edge set if and only if the edge connecting them belongs to the set and the two vertices are distinct.
SimpleGraph.top_adj- Two vertices are adjacent in the complete graph if and only if they are distinct.
Sym2.eq- Two unordered pairs are equal if and only if their elements are pairwise equal in the same or reversed order.
Fin.exists_fin_succ- An existential statement over Fin (n + 1) is equivalent to the property holding for 0 or for some successor.
SimpleGraph.neighborSet- The definition of the set of neighbors of a vertex in a simple graph.
ne_comm- Inequality is symmetric: a ≠ b if and only if b ≠ a.
Nat.card_coe_set_eq- The cardinality of a subtype coerced from a set equals the set's noncomputable cardinality.
op223_triangle_neighbors- In the complete graph on 3 vertices, the neighbor set of any vertex x is the set of all vertices except x.
Set.ncard_coe_finset- The set cardinality of a coerced finite set equals its Finset cardinality.
op223_triangle_shift_graph- The shifted graph op223_triangle_shift has edge set {{0, 1}, {0, 2}}.
SimpleGraph.mem_neighborSet- A vertex w belongs to the neighbor set of v if and only if v and w are adjacent.
Finset.card_insert_eq_ite- Inserting an element into a finite set increases its cardinality by 1 if the element was not already present, and leaves it unchanged otherwise.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
op223_triangle_degree- Every vertex in the complete graph on 3 vertices has degree 2.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set.
true_and- Conjunction with True is equivalent to the proposition itself.
Finset.mem_singleton- An element belongs to a singleton set if and only if it equals the sole member.
op223_triangle_shift_degree_zero- In the shifted graph, vertex 0 has degree 2.
op223_triangle_shift_degree_one- In the shifted graph, vertex 1 has degree 1.
op223_triangle_shift_degree_two- In the shifted graph, vertex 2 has degree 1.
Finset.filter_true_of_mem- Filtering a finite set by a predicate that holds for all its elements yields the set itself.
- Determining the edge set and vertex degrees of the shifted graph is carried out by exhaustive case analysis over all vertices and pairs of vertices in Fin 3 using `fin_cases` and `decide`, replacing the paper-level observation that shifting the edge {1, 2} to {0, 2} collapses it into an already existing edge of K₃.
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_triangle : SimpleGraph (Fin 3) := ⊤def op223_triangle_shift : SimpleGraph (Fin 3) := gts_graph op223_triangle 0 1 0theorem op223_triangle_shift_graph : op223_triangle_shift = SimpleGraph.fromEdgeSet {s(0,1), s(0,2)} := by ext a b fin_cases a <;> fin_cases b <;> simp only [op223_triangle_shift, op223_triangle, gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Set.mem_setOf_eq, Set.mem_insert_iff, Set.mem_singleton_iff, SimpleGraph.top_adj, Sym2.eq, Fin.exists_fin_succ] <;> decidelemma op223_triangle_neighbors (x : Fin 3) : op223_triangle.neighborSet x = ((Finset.univ.erase x : Finset (Fin 3)) : Set (Fin 3)) := by ext y simp [op223_triangle, SimpleGraph.neighborSet, SimpleGraph.top_adj, ne_comm]lemma op223_triangle_degree (x : Fin 3) : Nat.card (op223_triangle.neighborSet x) = 2 := by rw [Nat.card_coe_set_eq, op223_triangle_neighbors, Set.ncard_coe_finset] simplemma op223_triangle_shift_degree_zero : Nat.card (op223_triangle_shift.neighborSet 0) = 2 := by have h : op223_triangle_shift.neighborSet 0 = (({1,2} : Finset (Fin 3)) : Set (Fin 3)) := by rw [op223_triangle_shift_graph] ext x; fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_insert_iff, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] <;> decide rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset] norm_num [Finset.card_insert_eq_ite, Fin.ext_iff]lemma op223_triangle_shift_degree_one : Nat.card (op223_triangle_shift.neighborSet 1) = 1 := by have h : op223_triangle_shift.neighborSet 1 = (({0} : Finset (Fin 3)) : Set (Fin 3)) := by rw [op223_triangle_shift_graph] ext x; fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_insert_iff, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] <;> decide rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset] norm_numlemma op223_triangle_shift_degree_two : Nat.card (op223_triangle_shift.neighborSet 2) = 1 := by have h : op223_triangle_shift.neighborSet 2 = (({0} : Finset (Fin 3)) : Set (Fin 3)) := by rw [op223_triangle_shift_graph] ext x; fin_cases x <;> simp only [SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Set.mem_insert_iff, Set.mem_singleton_iff, Sym2.eq, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] <;> decide rw [Nat.card_coe_set_eq,h,Set.ncard_coe_finset] norm_numtheorem op223_nonleaf_count_counterexample : ∃ (T : SimpleGraph (Fin 3)) (u v : Fin 3), T.Adj u v ∧ 2 ≤ Nat.card (T.neighborSet u) ∧ 2 ≤ Nat.card (T.neighborSet v) ∧ (Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card ((gts_graph T u v u).neighborSet x))).card + 1 < (Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (T.neighborSet x))).card := by refine ⟨op223_triangle, 0, 1, ?_, ?_, ?_, ?_⟩ · simp [op223_triangle] · rw [op223_triangle_degree] · rw [op223_triangle_degree] · change (Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (op223_triangle_shift.neighborSet x))).card + 1 < (Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (op223_triangle.neighborSet x))).card have hf : Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (op223_triangle_shift.neighborSet x)) = {0} := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton] fin_cases x · change (1 < Nat.card (op223_triangle_shift.neighborSet 0)) ↔ (0 : Fin 3) = 0 rw [op223_triangle_shift_degree_zero]; decide · change (1 < Nat.card (op223_triangle_shift.neighborSet 1)) ↔ (1 : Fin 3) = 0 rw [op223_triangle_shift_degree_one]; decide · change (1 < Nat.card (op223_triangle_shift.neighborSet 2)) ↔ (2 : Fin 3) = 0 rw [op223_triangle_shift_degree_two]; decide have hg : Finset.univ.filter (fun x : Fin 3 => 1 < Nat.card (op223_triangle.neighborSet x)) = Finset.univ := by apply Finset.filter_true_of_mem intro x hx rw [op223_triangle_degree] decide rw [hf, hg] simp