AFTD Auto-Formalizing Theoretical Domains

ArrowsIsSource

def

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

Statement

def ArrowsIsSource {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

Given a finite type V, a simple graph G on V with decidable adjacency, an orientation p : ArrowsPos V (an asymmetric relation p : V → V → Bool where p x y = true → p y x = false), and a vertex u : V, ArrowsIsSource G p u asserts that: 1. The degree of u in G is at least 1 (G.degree u ≥ 1), and 2. For every vertex v : V, if u is adjacent to v in G, then the edge is oriented from u to v (that is, p.1 u v = 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 source in position p if degree u >= 1 and every neighbor v has an arrow out of u. -/
def ArrowsIsSource {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 u v
See it in the graphDiscuss this resultChallenge it