AFTD Auto-Formalizing Theoretical Domains

ArrowsIsSink

def

In a simple graph G and position p : ArrowsPos V, vertex u is a sink if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1 v u is true.

Statement

def ArrowsIsSink {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p : ArrowsPos V) (u : V) : Prop
Defined in
arXiv:2610.15145 Section 2.2
Verified
24 Oct 2026
Axioms
none listed
Built on 1
  • ArrowsPosGiven a type V, ArrowsPos V is the subtype of boolean-valued binary relations p : V → V → Bool that are asymmetric, meaning that for all…
Used by 4
  • ArrowsLegalMoveIn a simple graph G, a transition from position p to q in ArrowsPos V is a legal move if there exist u, v with ArrowsUnmarked G p u v such…
  • arrows_markable_unmarked_of_legalEvery legal move of the Game of Arrows decreases the number of unmarked markable edges by exactly one.
  • arrows_legal_move_degree_ne_oneIf marking the unmarked edge uv as u -> v leaves u not a source and v not a sink, then neither u nor v has degree 1 (pendant edges can…
  • arrows_legal_move_decidableFor a finite graph with decidable equality and decidable adjacency, whether q is a legal option of p is decidable.

Read back from the Lean

For a finite type V, a simple graph G on V with decidable adjacency, an asymmetric relation p : ArrowsPos V, and a vertex u : V, ArrowsIsSink G p u asserts that: 1. The degree of u in G is at least 1 (G.degree u ≥ 1), and 2. For all vertices v : V, if u and v are adjacent in G (G.Adj u v), then p.1 v u holds (evaluates to true).

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

/-- Vertex u is a sink in position p if degree u >= 1 and every neighbor v has an arrow into u. -/
def ArrowsIsSink {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (p : ArrowsPos V) (u : V) : Prop := G.degree u ≥ 1 ∧ ∀ v, G.Adj u v → p.1 v u
See it in the graphDiscuss this resultChallenge it