simple_graph_has_modulo_orientation
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
- empty_graph_has_modulo_orientationFor every natural number q, the empty simple graph on the empty type Empty has a modulo-q orientation.
- complete_twelve_no_modulo_seven_orientationThe complete graph on 12 vertices does not have a modulo-7 orientation.
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))