mixed_graph_has_cycle
def
A 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 an edge or by an arc directed from x_i to x_{i+1}.
Statement
def mixed_graph_has_cycle {V : Type*} (E : SimpleGraph V) (A : V → V → Prop) (t : ℕ) : Prop
- Defined in
- arXiv:2610.14110 (New mixed cages, bounds and computational results), Sec. 2 (cycles of a mixed graph).
- Verified
- 17 Oct 2026
- Axioms
- none listed
- Used by 8
- mixed_graph_has_cycle_directed_triangleSanity check: the directed triangle 0 → 1 → 2 → 0 has a 3-cycle.
- mixed_graph_has_girthA mixed graph has girth g: it has a cycle of length g and no shorter cycle.
- 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_cycle_g_existsFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N(z, g) vertices has a mixed cycle of length g: when z is even, g - 1 arc steps of jump…
- mixed_graph_has_girth_directed_triangleSanity check: the directed triangle has girth 3.
- 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…
- circulant_mixed_graph_no_cycle_lt_gFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N(z, g) vertices contains no mixed cycle of length t < g.
Lean source view module on GitHub
/-- `(E, A)` has a `t`-cycle: `t ≥ 3` pairwise distinct vertices `x 0, ..., x (t-1)` with an edge `x i — x (i+1)` or an arc `x i → x (i+1)` for every `i`, indices mod `t` (`finRotate`). The paper notes cycles have length at least 3: with distinct vertices no edge is used twice. -/ def mixed_graph_has_cycle {V : Type*} (E : SimpleGraph V) (A : V → V → Prop) (t : ℕ) : Prop := 3 ≤ t ∧ ∃ x : Fin t → V, Function.Injective x ∧ ∀ i : Fin t, E.Adj (x i) (x (finRotate t i)) ∨ A (x i) (x (finRotate t i))