AFTD Auto-Formalizing Theoretical Domains

gts_graph

def

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

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 }
See it in the graphDiscuss this resultChallenge it