AFTD Auto-Formalizing Theoretical Domains

mixed_graph_is_regular

def

A mixed graph is (r, z)-regular when every vertex has r neighbours along edges, z out-neighbours and z in-neighbours along arcs.

Statement

def mixed_graph_is_regular {V : Type*} (E : SimpleGraph V) (A : V → V → Prop) (r z : ℕ) : Prop
Defined in
arXiv:2610.14110 (New mixed cages, bounds and computational results), Sec. 2 ((r,z)-regular, also called totally regular).
Verified
17 Oct 2026
Axioms
none listed
Used by 5
  • mixed_graph_card_ge_of_is_regularEvery (r, z)-regular mixed graph on a finite nonempty vertex set has at least r + 2z + 1 vertices.
  • mixed_cage_ordern(r, z, g): the minimum order of an (r, z)-regular mixed graph of girth g (the order of an (r, z, g)-mixed cage).
  • mixed_cage_order_girth_threeFor all r ≥ 1 and z ≥ 1, the minimum order of an (r, z, 3)-mixed cage is n(r, z, 3) = r + 2z + 1.
  • circulant_mixed_graph_valid_and_regularFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N = N(z, g) vertices with antipodal edges of jump m = N/2 and arc jumps 1..⌈z/2⌉ and…
  • mixed_cage_order_one_leFor z ≥ 1 and g ≥ 3, n(1, z, g) ≤ N(z, g), where N(z, g) = z(g − 1) + 2 for even z and (z + 1)(g − 1) for odd z: the circulant M(z, g) on…

Lean source view module on GitHub

/-- `(E, A)` is `(r, z)`-regular: every vertex has degree `r` in `E`, out-degree `z` and in-degree `z` in `A` (cardinalities as `Set.ncard`, meant for finite `V`). -/
def mixed_graph_is_regular {V : Type*} (E : SimpleGraph V) (A : V → V → Prop) (r z : ℕ) : Prop :=
  ∀ x, {y | E.Adj x y}.ncard = r ∧ {y | A x y}.ncard = z ∧ {y | A y x}.ncard = z
See it in the graphDiscuss this resultChallenge it