AFTD Auto-Formalizing Theoretical Domains

op223_nonleaf_count_counterexample

theoremverifiedoriginal

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.

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

    lines 9–14

    uses SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.top_adj, Sym2.eq, Fin.exists_fin_succ

      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] <;> decide
  2. 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}.

    lines 18–19

    uses SimpleGraph.neighborSet, SimpleGraph.top_adj, ne_comm

      ext y
      simp [op223_triangle, SimpleGraph.neighborSet, SimpleGraph.top_adj, ne_comm]
  3. 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.

    lines 22–23

    uses Nat.card_coe_set_eq, op223_triangle_neighbors, Set.ncard_coe_finset

      rw [Nat.card_coe_set_eq, op223_triangle_neighbors, Set.ncard_coe_finset]
      simp
  4. 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.

    lines 26–32

    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_iff

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

    lines 35–41

    uses op223_triangle_shift_graph, SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Nat.card_coe_set_eq, Set.ncard_coe_finset

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

    lines 44–50

    uses op223_triangle_shift_graph, SimpleGraph.mem_neighborSet, SimpleGraph.fromEdgeSet_adj, Nat.card_coe_set_eq, Set.ncard_coe_finset

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

    lines 57–60

    uses op223_triangle_degree

      refine ⟨op223_triangle, 0, 1, ?_, ?_, ?_, ?_⟩
      · simp [op223_triangle]
      · rw [op223_triangle_degree]
      · rw [op223_triangle_degree]
  8. 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}.

    lines 61–72

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

    lines 73–77

    uses Finset.filter_true_of_mem, op223_triangle_degree

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

    lines 78–79

        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.

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