mixed_graph_is_valid
def
A mixed graph on V: undirected edges E (a simple graph) and arcs A, with no loops and at most one edge or arc between two vertices (no antiparallel arcs, no arc parallel to an edge).
Statement
def mixed_graph_is_valid {V : Type*} (E : SimpleGraph V) (A : V → V → Prop) : Prop
- Defined in
- arXiv:2610.14110 (New mixed cages, bounds and computational results), Sec. 2 (mixed graphs: edges and arcs, no loops, at most one edge or arc between two vertices).
- Verified
- 17 Oct 2026
- Axioms
- none listed
- Used by 6
- 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_graph_is_valid_directed_triangleSanity check: the directed triangle is a mixed graph (no loops, no antiparallel arcs).
- 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 a mixed graph: `A` is irreflexive and asymmetric (no antiparallel arcs) and no arc joins two vertices joined by an edge. `E` is a `SimpleGraph`, so it has no loops or parallel edges. -/ def mixed_graph_is_valid {V : Type*} (E : SimpleGraph V) (A : V → V → Prop) : Prop := (∀ x, ¬ A x x) ∧ (∀ x y, A x y → ¬ A y x) ∧ ∀ x y, E.Adj x y → ¬ A x y