is_generalized_tree_shift
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