AFTD Auto-Formalizing Theoretical Domains

mixed_graph_has_girth

def

A mixed graph has girth g: it has a cycle of length g and no shorter cycle.

Statement

def mixed_graph_has_girth {V : Type*} (E : SimpleGraph V) (A : V → V → Prop) (g : ℕ) : Prop
Defined in
arXiv:2610.14110 (New mixed cages, bounds and computational results), Sec. 2 (girth of a mixed graph).
Verified
17 Oct 2026
Axioms
none listed
Built on 1
  • mixed_graph_has_cycleA mixed graph has a cycle of length t ≥ 3: distinct vertices x_0, ..., x_{t-1} such that each x_i is joined to x_{i+1} (indices mod t) by…
Used by 4

Lean source view module on GitHub

/-- `(E, A)` has girth `g`: a `g`-cycle exists and no `t`-cycle with `t < g` does. -/
def mixed_graph_has_girth {V : Type*} (E : SimpleGraph V) (A : V → V → Prop) (g : ℕ) : Prop :=
  mixed_graph_has_cycle E A g ∧ ∀ t < g, ¬ mixed_graph_has_cycle E A t
See it in the graphDiscuss this resultChallenge it