AFTD Auto-Formalizing Theoretical Domains

op223_adjacent_is_generalized_tree_shift

theoremverified

For 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 generalized tree shift of T.

Statement

theorem op223_adjacent_is_generalized_tree_shift {V : Type*}
  (T : SimpleGraph V) (hT : T.IsTree) (u v : V) (huv : T.Adj u v) :
  is_generalized_tree_shift T (gts_graph T u v u)
Source
step towards nonsustainable_tree_has_nonsustainable_successor_closer_to_star
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • gts_graphThe graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between…
  • 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…
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

A generalized tree shift along a path p from u to v shifts all neighbors of v other than p's penultimate vertex to u, requiring that all internal vertices of p have degree 2 in T. When u and v are already adjacent, the single edge (u, v) is chosen as the path. This path of length 1 has no internal vertices, making the degree condition vacuously true, and its penultimate vertex is u, which matches the definition of gts_graph T u v u.

  1. It suffices to check the generalized tree shift conditions using the single-edge walk from u to v as the witness path.

    The definition of is_generalized_tree_shift requires a tree T, two distinct vertices u and v, and a path between them whose internal vertices have degree 2, such that the shifted graph matches gts_graph with the penultimate vertex of the path. We provide the tree hypothesis hT, vertices u and v, and the single-edge walk SimpleGraph.Walk.cons huv SimpleGraph.Walk.nil from u to v. The vertices u and v are distinct because adjacent vertices in a simple graph are never equal (huv.ne). This reduces the goal to three remaining obligations: the walk is a path, its internal vertices have degree 2, and the resulting shift matches the definition.

    line 7

    uses SimpleGraph.Walk.cons, SimpleGraph.Walk.nil

      refine ⟨hT, u, v, SimpleGraph.Walk.cons huv SimpleGraph.Walk.nil, ?_, huv.ne, ?_, ?_⟩
  2. The single-edge walk from u to v is a path.

    The trivial walk at v is a path, and prepending the edge from u to v yields a path provided u is not in the support of the trivial walk (which consists solely of v). Since u ≠ v by the adjacency hypothesis, this non-membership condition holds, confirming the single-edge walk is a path.

    line 8

    uses SimpleGraph.Walk.IsPath.nil.cons

      · exact SimpleGraph.Walk.IsPath.nil.cons (by simpa using huv.ne)
  3. All internal vertices of the walk have degree 2 in T.

    An internal vertex x on the path would have to be in the walk's support while satisfying x ≠ u and x ≠ v. Simplifying the support of the single-edge walk shows that it contains only u and v (x = u ∨ x = v). Both cases contradict the distinctness assumptions x ≠ u and x ≠ v, so the degree condition is vacuously satisfied.

    lines 9–12

    uses SimpleGraph.Walk.support_cons, SimpleGraph.Walk.support_nil, List.mem_cons, List.not_mem_nil, or_false

      · intro x hx hxu hxv
        simp only [SimpleGraph.Walk.support_cons, SimpleGraph.Walk.support_nil, List.mem_cons,
          List.not_mem_nil, or_false] at hx
        rcases hx with rfl | rfl <;> contradiction
  4. The penultimate vertex of the single-edge walk is u, so the graph matches the definition.

    For a walk consisting of a single edge from u to v, the penultimate vertex is definitionally u. Thus, the target graph gts_graph T u v u is definitionally equal to gts_graph T u v (Walk.cons huv Walk.nil).penultimate, closing the proof by reflexivity.

    line 13

      · rfl
SimpleGraph.Walk.cons
Extends a walk by prepending an edge between adjacent vertices.
SimpleGraph.Walk.nil
The trivial walk of length 0 from a vertex to itself.
SimpleGraph.Walk.IsPath.nil.cons
Extending the trivial walk at v by an edge from u to v yields a path, provided u does not belong to the support of the trivial walk (i.e., u ≠ v).
SimpleGraph.Walk.support_cons
The vertex support of a walk prepended with an edge from u to v starts with u followed by the support of the rest of the walk.
SimpleGraph.Walk.support_nil
The vertex support of the trivial walk at vertex u is the singleton list [u].
List.mem_cons
An element belongs to the list b :: l if and only if it equals b or belongs to l.
List.not_mem_nil
The empty list contains no elements.
or_false
Disjoining a proposition with False is equivalent to the proposition itself.

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 SimpleGraph/-- For 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 generalized tree shift of T. -/theorem op223_adjacent_is_generalized_tree_shift {V : Type*}  (T : SimpleGraph V) (hT : T.IsTree) (u v : V) (huv : T.Adj u v) :  is_generalized_tree_shift T (gts_graph T u v u) := by  refine ⟨hT, u, v, SimpleGraph.Walk.cons huv SimpleGraph.Walk.nil, ?_, huv.ne, ?_, ?_⟩  · exact SimpleGraph.Walk.IsPath.nil.cons (by simpa using huv.ne)  · intro x hx hxu hxv    simp only [SimpleGraph.Walk.support_cons, SimpleGraph.Walk.support_nil, List.mem_cons,      List.not_mem_nil, or_false] at hx    rcases hx with rfl | rfl <;> contradiction  · rfl
See it in the graphDiscuss this resultChallenge it