AFTD Auto-Formalizing Theoretical Domains

op223_gts_neighbor_sets_counterexample

theoremverifiedoriginal

There is a graph on four vertices with adjacent u and v and a third vertex x whose neighbor set changes after the generalized tree shift from v to u.

Statement

theorem op223_gts_neighbor_sets_counterexample :
    ∃ (T : SimpleGraph (Fin 4)) (u v x : Fin 4),
      T.Adj u v ∧ x ≠ u ∧ x ≠ v ∧
      (gts_graph T u v u).neighborSet x ≠ T.neighborSet x
Related work
arXiv:2610.17078 Open Problem 6.1; counterexamples to auxiliary statements
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 $\text{Fin } 4$ and vertices $u, v, x \in \text{Fin } 4$ such that: 1. $u$ and $v$ are adjacent in $T$, 2. $x \neq u$, 3. $x \neq v$, and 4. the neighbor set of $x$ in $\text{gts\_graph}(T, u, v, u)$ is not equal to the neighbor set of $x$ in $T$.

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

We exhibit an explicit counterexample using the path graph on four vertices {0, 1, 2, 3} with adjacent vertices u = 1 and v = 2, and a third vertex x = 3. Under the generalized tree shift from v to u with pivot u, all incident edges to v other than {u, v} are detached and redirected to u, deleting the edge {2, 3} and replacing it with {1, 3}. Assuming for contradiction that the neighbor set of x = 3 remains unchanged would force {2, 3} to remain an edge, which directly contradicts the edge deletion.

  1. The path graph on 4 vertices with u = 1, v = 2, and x = 3 satisfies the conditions u ~ v, x ≠ u, and x ≠ v.

    We provide the 4-vertex path graph P₄ on vertices {0, 1, 2, 3} with vertices u = 1, v = 2, and x = 3 as the witness. The distinctness requirements 3 ≠ 1 and 3 ≠ 2 hold immediately by finite decision (decide). Adjacency 1 ~ 2 in P₄ holds because |1 - 2| = 1, verified by arithmetic via SimpleGraph.pathGraph_adj.

    lines 8–9

    uses SimpleGraph.pathGraph_adj

      refine ⟨SimpleGraph.pathGraph 4, 1, 2, 3, ?_, by decide, by decide, ?_⟩
      · norm_num [SimpleGraph.pathGraph_adj]
  2. If the neighbor set of vertex 3 were preserved under the generalized tree shift, then 3 would still be adjacent to 2 in the shifted graph.

    We assume for contradiction that the neighbor set of vertex 3 is unchanged by the shift (intro h). In the original path graph P₄, vertex 3 is adjacent to vertex 2 (hv, via SimpleGraph.pathGraph_adj), so 2 is in the neighbor set of 3. Under the assumption h that the neighbor set is preserved, 2 must also belong to the neighbor set of 3 in the shifted graph, which means 3 and 2 are adjacent in that graph (hnew).

    lines 10–15

    uses SimpleGraph.pathGraph_adj

      · intro h
        have hv : (SimpleGraph.pathGraph 4).Adj 3 2 := by norm_num [SimpleGraph.pathGraph_adj]
        have hnew : (gts_graph (SimpleGraph.pathGraph 4) 1 2 1).Adj 3 2 := by
          have hm : (2 : Fin 4) ∈ (SimpleGraph.pathGraph 4).neighborSet 3 := hv
          rw [← h] at hm
          exact hm
  3. Vertex 3 is not adjacent to 2 in the shifted graph, yielding a contradiction.

    We expand and simplify the adjacency condition hnew using the definition of gts_graph and lemmas characterising adjacency in graph unions (SimpleGraph.sup_adj), edge deletions (SimpleGraph.deleteEdges_adj), and edge-set graphs (SimpleGraph.fromEdgeSet_adj), along with path graph adjacency (SimpleGraph.pathGraph_adj), unordered pair equality (Sym2.eq), and Fin equality (Fin.ext_iff). In the shift from v = 2 to u = 1 with pivot 1, all edges at 2 other than {2, 1} are deleted and redirected to 1; thus {2, 3} is removed. Simplification reduces hnew to the statement that any vertex equal to 3 must be equal to 1. Specialising this to vertex 3 gives 3 = 1, which norm_num refutes to complete the contradiction.

    lines 16–19

    uses SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.pathGraph_adj, Sym2.eq, Fin.ext_iff

        simp [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj,
          SimpleGraph.fromEdgeSet_adj, SimpleGraph.pathGraph_adj, Sym2.eq, Fin.ext_iff] at hnew
        specialize hnew 3
        norm_num at hnew
SimpleGraph.pathGraph_adj
Two vertices in a path graph 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 graphs.
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 their connecting edge was not deleted.
SimpleGraph.fromEdgeSet_adj
Two vertices are adjacent in a graph defined from an edge set if and only if they are distinct and their connecting edge is in the set.
Sym2.eq
Two unordered pairs of vertices are equal if and only if their elements match up to order.
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.

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 Classicaltheorem op223_gts_neighbor_sets_counterexample :    ∃ (T : SimpleGraph (Fin 4)) (u v x : Fin 4),      T.Adj u v ∧ x ≠ u ∧ x ≠ v ∧      (gts_graph T u v u).neighborSet x ≠ T.neighborSet x := by  refine ⟨SimpleGraph.pathGraph 4, 1, 2, 3, ?_, by decide, by decide, ?_⟩  · norm_num [SimpleGraph.pathGraph_adj]  · intro h    have hv : (SimpleGraph.pathGraph 4).Adj 3 2 := by norm_num [SimpleGraph.pathGraph_adj]    have hnew : (gts_graph (SimpleGraph.pathGraph 4) 1 2 1).Adj 3 2 := by      have hm : (2 : Fin 4) ∈ (SimpleGraph.pathGraph 4).neighborSet 3 := hv      rw [← h] at hm      exact hm    simp [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj,      SimpleGraph.fromEdgeSet_adj, SimpleGraph.pathGraph_adj, Sym2.eq, Fin.ext_iff] at hnew    specialize hnew 3    norm_num at hnew
See it in the graphDiscuss this resultChallenge it