AFTD Auto-Formalizing Theoretical Domains

game_of_arrows_legal_move

def

A move from position P to Q in the Game of Arrows on graph G is legal if an unmarked edge between adjacent vertices u and v is oriented as (u, v) in Q, and neither u nor v is a sink or source in Q.

Statement

def game_of_arrows_legal_move {V : Type} [DecidableEq V] (G : SimpleGraph V) (P Q : ArrowsPosition V G) : Prop
Defined in
arXiv:2610.15145 Section 2.2
Verified
24 Oct 2026
Axioms
none listed
Built on 3
  • ArrowsPositionA position in the Game of Arrows on a simple graph G consists of a finite set of directed edges (arrows) between vertices adjacent in G,…
  • game_of_arrows_is_sinkIn a position P of the Game of Arrows on graph G, a vertex v is a sink if v has at least one incident edge and every incident edge points…
  • game_of_arrows_is_sourceIn a position P of the Game of Arrows on graph G, a vertex v is a source if v has at least one incident edge and every incident edge…

Read back from the Lean

Given a type V with decidable equality, a simple graph G on V, and two arrow positions P and Q (where an arrow position consists of a finite set of directed edges that are edges of G with no edge oriented in both directions), game_of_arrows_legal_move G P Q asserts that there exist vertices u, v : V such that: 1. u and v are adjacent in G; 2. neither (u, v) nor (v, u) is in P.arrows (the edge between u and v is unoriented in P); 3. Q.arrows is obtained by inserting the directed edge (u, v) into P.arrows; 4. u is not a sink in Q (it does not have at least one neighbor with all incident edges directed towards u); 5. u is not a source in Q (it does not have at least one neighbor with all incident edges directed away from u); 6. v is not a sink in Q; and 7. v is not a source in Q.

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 transition from position P to Q in the Game of Arrows is a legal move if Q adds an oriented edge without making either endpoint a sink or source. -/
def game_of_arrows_legal_move {V : Type} [DecidableEq V] (G : SimpleGraph V) (P Q : ArrowsPosition V G) : Prop := ∃ (u v : V), G.Adj u v ∧ (u, v) ∉ P.arrows ∧ (v, u) ∉ P.arrows ∧
    Q.arrows = insert (u, v) P.arrows ∧
    ¬ game_of_arrows_is_sink G Q u ∧ ¬ game_of_arrows_is_source G Q u ∧
    ¬ game_of_arrows_is_sink G Q v ∧ ¬ game_of_arrows_is_source G Q v
See it in the graphDiscuss this resultChallenge it