AFTD Auto-Formalizing Theoretical Domains

op223_adjacent_shift_retains_beneficiary_edges

theoremverified

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

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

    lines 6–9

    uses SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj

      classical
      simp only [gts_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj]
      left
      refine ⟨huw, ?_⟩
  2. 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).

    lines 10–11

    uses Sym2.eq_iff.mp

      rintro ⟨z, hz, hvz, hzu⟩
      rcases Sym2.eq_iff.mp hz with ⟨huv', hwz⟩ | ⟨huz, hwv⟩
  3. 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.

    line 12

      · exact huv.ne huv'
  4. 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.

    line 13

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

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