gts_graph
The graph obtained from T by deleting all edges between candidate v and its neighbours other than w, and inserting edges between beneficiary u and those neighbours.
Statement
def gts_graph {V : Type*} (T : SimpleGraph V) (u v w : V) : SimpleGraph V
- Defined in
- arXiv:2610.17078 Section 2
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 10
- 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_tree_adjacent_shift_nonleaf_countIf both endpoints of an edge of a finite tree have degree at least two, shifting along that edge reduces the number of non-leaf vertices…
- op223_nonleaf_count_counterexampleThere is a graph on three vertices with adjacent u and v of degree at least two for which the adjacent shift reduces the number of…
- 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…
- op223_adjacent_shift_retains_beneficiary_edgesAn adjacent generalized tree shift retains every edge incident to its beneficiary.
- op223_gts_neighbor_sets_counterexampleThere is a graph on four vertices with adjacent u and v and a third vertex x whose neighbor set changes after the generalized tree shift…
- op223_tree_adjacent_shift_other_degreesAn adjacent generalized shift in a finite tree preserves the degree of every vertex other than its two endpoints.
- 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…
- 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
Given a type V, a simple graph T on V, and vertices u, v, w : V, gts_graph T u v w defines a new SimpleGraph V. It is the join (union, ⊔) of:
1. T with all edges of the form s(v, z) deleted, where z is a neighbor of v in T and z ≠ w; and
2. The simple graph constructed from the edge set of all pairs s(u, z) where z is a neighbor of v in T and z ≠ w.
In other words, it performs a generalized tree shift (GTS) on T, redirecting all edges incident to v (except possibly the edge to w) to instead be incident to u.
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
/-- The graph formed by removing all edges between v and N(v) \ {w} and adding edges between u and N(v) \ {w}. -/ def gts_graph {V : Type*} (T : SimpleGraph V) (u v w : V) : SimpleGraph V := T.deleteEdges { e | ∃ z, e = s(v, z) ∧ T.Adj v z ∧ z ≠ w } ⊔ SimpleGraph.fromEdgeSet { e | ∃ z, e = s(u, z) ∧ T.Adj v z ∧ z ≠ w }