op223_adjacent_shift_retains_beneficiary_edges
An adjacent generalized tree shift retains every edge incident to its beneficiary.
Statement
theorem op223_adjacent_shift_retains_beneficiary_edges {V : Type*} (T : SimpleGraph V) (u v w : V) (huv : T.Adj u v) (huw : T.Adj u w) : (gts_graph T u v u).Adj u w
- Source
- arXiv:2610.17078 Open Problem 6.1
- 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…
- Used by 1
- op223_shift_bad_edge_yields_stepIf a nonsustainable tree undergoes an adjacent shift and a retained beneficiary edge remains nonsustainable, the shift is a step between…
The proof, explained
To show that an adjacent generalized tree shift retains the edge {u, w} incident to the beneficiary u, it suffices to show that {u, w} was not deleted during the shift. The shift deletes only edges incident to the donor v whose other endpoint is distinct from u. If {u, w} were among the deleted edges, then as unordered pairs {u, w} = {v, z} with z ≠ u, implying either u = v (contradicting adjacency of u and v) or u = z (contradicting z ≠ u).
To show that u and w are adjacent in the shifted graph, it suffices to show that the edge {u, w} was not deleted from T.
By definition, the adjacent generalized tree shift gts_graph(T, u, v, u) is the union of T with a set of deleted edges and a set of newly added edges. An edge is present in this union if it survives in the edge-deleted graph. Since {u, w} is already an edge of T (by hypothesis huw), it suffices to verify that {u, w} does not belong to the set of edges deleted during the shift, namely { {v, z} | T.Adj v z and z ≠ u }.
uses
SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adjclassical simp only [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj] left refine ⟨huw, ?_⟩
Assuming for contradiction that {u, w} was deleted, either u = v and w = z, or u = z and w = v, for some vertex z adjacent to v with z ≠ u.
Suppose for contradiction that {u, w} belongs to the deleted edge set. Then {u, w} = {v, z} as unordered pairs for some vertex z satisfying T.Adj v z and z ≠ u. By Sym2.eq_iff.mp, equality of two unordered pairs means either their endpoints match directly (u = v and w = z) or they are swapped (u = z and w = v).
uses
Sym2.eq_iff.mprintro ⟨z, hz, hvz, hzu⟩ rcases Sym2.eq_iff.mp hz with ⟨huv', hwz⟩ | ⟨huz, hwv⟩
The case u = v is impossible.
In a simple graph, adjacency is irreflexive: since u is adjacent to v (hypothesis huv), u ≠ v, which contradicts u = v.
· exact huv.ne huv'The case u = z is impossible, completing the proof.
The condition defining the deleted edge set required z ≠ u (hypothesis hzu), which directly contradicts u = z.
· exact hzu huz.symm
SimpleGraph.sup_adj- Two vertices are adjacent in the union (supremum) of two graphs if and only if they are adjacent in the first graph or the second graph.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent in a graph after deleting a set of edges if and only if they were adjacent in the original graph and the edge connecting them was not in the deleted set.
Sym2.eq_iff.mp- If two unordered pairs are equal, {a, b} = {c, d}, then either a = c and b = d, or a = d and b = c.
- The proof uses `classical` on line 6 to enable classical reasoning for set membership and decidability, a formal detail with no counterpart on paper.
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 SimpleGraphtheorem op223_adjacent_shift_retains_beneficiary_edges {V : Type*} (T : SimpleGraph V) (u v w : V) (huv : T.Adj u v) (huw : T.Adj u w) : (gts_graph T u v u).Adj u w := by classical simp only [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj] left refine ⟨huw, ?_⟩ rintro ⟨z, hz, hvz, hzu⟩ rcases Sym2.eq_iff.mp hz with ⟨huv', hwz⟩ | ⟨huz, hwv⟩ · exact huv.ne huv' · exact hzu huz.symm