op223_gts_neighbor_sets_counterexample
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.
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.
uses
SimpleGraph.pathGraph_adjrefine ⟨SimpleGraph.pathGraph 4, 1, 2, 3, ?_, by decide, by decide, ?_⟩ · norm_num [SimpleGraph.pathGraph_adj]
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).
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
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.
uses
SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,SimpleGraph.pathGraph_adj,Sym2.eq,Fin.ext_iffsimp [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
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 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