AFTD Auto-Formalizing Theoretical Domains

op223_shift_bad_edge_yields_step

theoremverified

If a nonsustainable tree undergoes an adjacent shift and a retained beneficiary edge remains nonsustainable, the shift is a step between nonsustainable trees.

Statement

theorem op223_shift_bad_edge_yields_step {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) (hT : is_nonsustainable_tree T) (u v w : V)
    (huv : T.Adj u v) (huw : T.Adj u w)
    (hbad : ¬ is_sustainable_edge (gts_graph T u v u) s(u,w)) :
    nonsustainable_gts_step T (gts_graph T u v u)
Source
arXiv:2610.17078 Open Problem 6.1
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • op223_adjacent_shift_retains_beneficiary_edgesAn adjacent generalized tree shift retains every edge incident to its beneficiary.
  • op223_adjacent_is_generalized_tree_shiftFor any tree T and any adjacent vertices u, v, the graph gts_graph T u v u obtained by shifting all neighbours of v other than u to u is a…
  • op223_gts_is_treeFor any simple graphs T and T' on a type V, if T' is obtained from T by a generalized tree shift, then T' is a tree.
  • nonsustainable_gts_stepA transition step between two non-sustainable trees T and T' on a finite type V where T' is obtained from T by a generalized tree shift.
  • is_sustainable_edgeAn edge e in a tree T is sustainable if there exists a non-edge f such that T - e + f is a tree and the adjacency spectral radius of T - e…
  • is_nonsustainable_treeA tree T is non-sustainable if T is a tree and T is not sustainable.
  • is_generalized_tree_shiftA simple graph T' on an arbitrary type V is obtained from a tree T by a generalized tree shift if T is a tree, and there exist distinct…
  • gts_graphThe graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between…
  • is_sustainable_treeA tree T is sustainable if every edge of T is sustainable.
Used by 1

The proof, explained

To show that the adjacent shift produces a step between nonsustainable trees, we verify that the shifted graph is a tree, is obtained via a generalized tree shift, and is nonsustainable. The tree property and generalized tree shift property follow directly from general facts about adjacent shifts. Nonsustainability of the shifted graph is proved by contradiction: if it were sustainable, all its edges would be sustainable, contradicting the assumption that the retained edge $\{u, w\}$ is nonsustainable.

  1. The shifted graph is a generalized tree shift of $T$, is itself a tree, and retains the edge $\{u, w\}$.

    Because $u$ and $v$ are adjacent in the tree $T$, the adjacent shift from $v$ to $u$ is a generalized tree shift (by `op223_adjacent_is_generalized_tree_shift`). Since the operation is a generalized tree shift of a tree, the resulting graph is also a tree (by `op223_gts_is_tree`). Furthermore, the adjacent shift preserves preexisting edges at the recipient vertex $u$, so $\{u, w\}$ remains an edge in the shifted graph (by `op223_adjacent_shift_retains_beneficiary_edges`).

    lines 8–10

    uses op223_adjacent_is_generalized_tree_shift, op223_gts_is_tree, op223_adjacent_shift_retains_beneficiary_edges

      have hs := op223_adjacent_is_generalized_tree_shift T hT.1 u v huv
      have ht := op223_gts_is_tree T (gts_graph T u v u) hs
      have he := op223_adjacent_shift_retains_beneficiary_edges T u v w huv huw
  2. To prove that the adjacent shift is a step between nonsustainable trees, it suffices to show that the shifted graph is not sustainable.

    By definition, a step between nonsustainable trees requires that the starting tree $T$ is nonsustainable (given as an assumption), that the operation is a generalized tree shift (established as `hs`), and that the destination graph is a nonsustainable tree. Since the shifted graph is already known to be a tree (`ht`), only its failure to be sustainable remains to be checked.

    line 11

      refine ⟨hT, ⟨ht, ?_⟩, hs⟩
  3. The shifted graph is not sustainable, completing the proof.

    Suppose for contradiction that the shifted graph were sustainable (`intro h`). By definition, every edge in a sustainable tree must be sustainable. But $\{u, w\}$ is an edge of the shifted graph, so it would have to be sustainable, which directly contradicts the hypothesis `hbad`.

    lines 12–13

      intro h
      exact hbad (h.2 s(u,w) he)
op223_adjacent_is_generalized_tree_shift
For any tree $T$ and adjacent vertices $u$ and $v$, the adjacent shift graph $\text{gts\_graph}(T, u, v, u)$ is a generalized tree shift of $T$.
op223_gts_is_tree
If a graph $T'$ is obtained from a tree $T$ by a generalized tree shift, then $T'$ is also a tree.
op223_adjacent_shift_retains_beneficiary_edges
If $u$ is adjacent to both $v$ and $w$ in $T$, then $u$ and $w$ remain adjacent in the shifted graph $\text{gts\_graph}(T, u, v, u)$.

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_shift_bad_edge_yields_step {V : Type*} [Fintype V] [DecidableEq V]    (T : SimpleGraph V) (hT : is_nonsustainable_tree T) (u v w : V)    (huv : T.Adj u v) (huw : T.Adj u w)    (hbad : ¬ is_sustainable_edge (gts_graph T u v u) s(u,w)) :    nonsustainable_gts_step T (gts_graph T u v u) := by  have hs := op223_adjacent_is_generalized_tree_shift T hT.1 u v huv  have ht := op223_gts_is_tree T (gts_graph T u v u) hs  have he := op223_adjacent_shift_retains_beneficiary_edges T u v w huv huw  refine ⟨hT, ⟨ht, ?_⟩, hs⟩  intro h  exact hbad (h.2 s(u,w) he)
See it in the graphDiscuss this resultChallenge it