AFTD Auto-Formalizing Theoretical Domains

is_generalized_tree_shift

def

A 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 vertices u and v and a walk p from u to v in T that is a path, such that every vertex x in the support of p other than u and v has degree 2 (Nat.card (T.neighborSet x) = 2), and T' equals gts_graph T u v p.penultimate.

Statement

def is_generalized_tree_shift {V : Type*} (T T' : SimpleGraph V) : Prop
Defined in
arXiv:2610.17078 Section 2
Verified
18 Oct 2026
Axioms
none listed
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 8
  • 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…
  • sustainable_gts_stepA transition step between two sustainable trees T and T' on a finite type V where T' is obtained from T by a generalized tree shift.
  • 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…
  • nonsustainable_star_connectivity_of_ascent_stepIf every non-sustainable tree on Fin n (n ≥ 2) that is not a star has a non-sustainable generalized-tree-shift successor with strictly…
  • 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.
  • sustainable_path_connectivity_of_descent_stepIf every sustainable tree on Fin n (n ≥ 1) that is not a path has a sustainable generalized-tree-shift predecessor with strictly smaller…
  • op223_star_connectivity_from_edge_preservationAssume shifting along a nonsustainable edge preserves it, shifting a branch toward the center of a nonsustainable pendant edge preserves…
  • 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.

Read back from the Lean

For a type V and simple graphs T and T' on V, is_generalized_tree_shift T T' asserts that: 1. T is a tree (connected and acyclic); 2. There exist vertices u, v : V and a walk p from u to v in T such that: - p is a path (it visits no vertex more than once); - u ≠ v; - for every vertex x in the support of p (the list of vertices visited by p), if x ≠ u and x ≠ v, then the degree of x in T is 2 (specifically, Nat.card (T.neighborSet x) = 2); - T' is equal to gts_graph T u v p.penultimate.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A graph T' is obtained from a tree T by a generalized tree shift. -/
def is_generalized_tree_shift {V : Type*} (T T' : SimpleGraph V) : Prop := T.IsTree ∧ ∃ (u v : V) (p : T.Walk u v),
    p.IsPath ∧ u ≠ v ∧
    (∀ x ∈ p.support, x ≠ u → x ≠ v → Nat.card (T.neighborSet x) = 2) ∧
    T' = gts_graph T u v p.penultimate
See it in the graphDiscuss this resultChallenge it