AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_modulo_orientation

def

A simple graph G on a finite vertex set V has a modulo-q orientation if there exists an orientation directing each edge such that for every vertex v, its outdegree is congruent to its indegree modulo q.

Statement

def simple_graph_has_modulo_orientation {V : Type*} [Fintype V] (G : SimpleGraph V) (q : ℕ) : Prop
Defined in
arXiv:2610.07034 Sec. 1, p. 3
Verified
24 Oct 2026
Axioms
none listed
Used by 2

Read back from the Lean

Given a finite type V, a simple graph G on V, and a natural number q, simple_graph_has_modulo_orientation G q asserts that there exists a binary relation R : V → V → Prop such that: 1. For all u, v : V, if R u v, then u and v are adjacent in G; 2. For all u, v : V, if u and v are adjacent in G, then either (R u v and not R v u) or (R v u and not R u v) (that is, R is an orientation of G); 3. For every vertex v : V, the out-degree of v in R (the cardinality of {w : V | R v w}) is equal in ZMod q to the in-degree of v in R (the cardinality of {w : V | R w v}).

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 simple graph has a modulo-q orientation if there exists an orientation directing each edge such that at every vertex the outdegree is congruent to the indegree modulo q. -/
def simple_graph_has_modulo_orientation {V : Type*} [Fintype V] (G : SimpleGraph V) (q : ℕ) : Prop :=
  ∃ R : V → V → Prop,
    ((∀ u v, R u v → G.Adj u v) ∧
     (∀ u v, G.Adj u v → (R u v ∧ ¬ R v u ∨ R v u ∧ ¬ R u v))) ∧
    ∀ v : V,
      (open Classical in ((Finset.univ.filter (fun w => R v w)).card : ZMod q)) =
      (open Classical in ((Finset.univ.filter (fun w => R w v)).card : ZMod q))
See it in the graphDiscuss this resultChallenge it