mixed_graph_card_ge_of_is_regular
Every (r, z)-regular mixed graph on a finite nonempty vertex set has at least r + 2z + 1 vertices.
Statement
theorem mixed_graph_card_ge_of_is_regular {V : Type*} [Fintype V] [Nonempty V] (E : SimpleGraph V) (A : V → V → Prop) (r z : ℕ) (hv : mixed_graph_is_valid E A) (hr : mixed_graph_is_regular E A r z) : r + 2 * z + 1 ≤ Fintype.card V
- Formalizes
- arXiv:2610.14110 (New mixed cages, bounds and computational results), Theorem 3.1 (the lower bound n(r,z,g) ≥ r + 2z + 1 used for g = 3 in Theorem 5.1; here for every regular mixed graph).
- Verified
- 17 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- mixed_graph_is_validA 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…
- mixed_graph_is_regularA mixed graph is (r, z)-regular when every vertex has r neighbours along edges, z out-neighbours and z in-neighbours along arcs.
- Used by 1
- 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.
The proof, explained
To show that an (r, z)-regular mixed graph on a nonempty finite vertex set V has at least r + 2z + 1 vertices, pick an arbitrary vertex v and partition its local neighborhood into four sets: the vertex itself, its undirected neighbors, its directed out-neighbors, and its directed in-neighbors. The validity conditions of mixed graphs—no self-loops, no directed 2-cycles, and no shared undirected/directed edges—imply that these four sets are pairwise disjoint. By regularity, their cardinalities are 1, r, z, and z, respectively, so their union has size 1 + r + 2z. Since this union is a subset of V, its cardinality cannot exceed |V|, yielding r + 2z + 1 ≤ |V|.
Fix a vertex $v \in V$, unpack the structural and regularity properties at $v$, and define four candidate subsets $S_0, S_1, S_2, S_3$.
Since $V$ is nonempty, choose an arbitrary vertex $v \in V$. The simple graph condition implies $v$ has no loop in $E$ (`E.irrefl`). From the validity hypothesis `hv`, directed edges have no self-loops (`hv.1`), are asymmetric (`hv.2.1`), and do not coincide with undirected edges (`hv.2.2`). By $(r, z)$-regularity at $v$ (`hr v`), $v$ has $r$ undirected neighbors, $z$ out-neighbors, and $z$ in-neighbors. Finally, define the singleton $S_0 = \{v\}$, the undirected neighborhood $S_1 = \{y \mid E.\mathrm{Adj}(v, y)\}$, the out-neighborhood $S_2 = \{y \mid A(v, y)\}$, and the in-neighborhood $S_3 = \{y \mid A(y, v)\}$.
inhabit V let v : V := default have hE_loop : ¬E.Adj v v := E.irrefl have hA_loop : ¬A v v := hv.1 v have hA_asymm : ∀ x y, A x y → ¬A y x := hv.2.1 have hEA : ∀ x y, E.Adj x y → ¬A x y := hv.2.2 obtain ⟨hr1, hr2, hr3⟩ := hr v let S0 : Set V := {v} let S1 : Set V := {y | E.Adj v y} let S2 : Set V := {y | A v y} let S3 : Set V := {y | A y v}
$S_0$ and $S_1$ are disjoint.
By `Set.disjoint_left`, suppose an element $y \in S_0$ belongs to $S_1$. Since $y \in S_0$, $y = v$. Then $v \in S_1$ implies $E.\mathrm{Adj}(v, v)$, contradicting the irreflexivity of simple graphs (`hE_loop`).
uses
Set.disjoint_lefthave d01 : Disjoint S0 S1 := by rw [Set.disjoint_left] intro y hy1 hy2 cases hy1 exact hE_loop hy2
$S_0 \cup S_1$ and $S_2$ are disjoint.
By `Set.disjoint_left`, suppose $y \in S_0 \cup S_1$ also belongs to $S_2$, so $A(v, y)$. If $y \in S_0$, then $y = v$, yielding $A(v, v)$, which contradicts the absence of directed loops (`hA_loop`). If $y \in S_1$, then $E.\mathrm{Adj}(v, y)$, which contradicts $A(v, y)$ by the mutual exclusivity of undirected and directed edges (`hEA`).
uses
Set.disjoint_lefthave d02 : Disjoint (S0 ∪ S1) S2 := by rw [Set.disjoint_left] intro y hy1 hy2 rcases hy1 with rfl | hy1 · exact hA_loop hy2 · exact hEA v y hy1 hy2
$S_0 \cup S_1 \cup S_2$ and $S_3$ are disjoint.
By `Set.disjoint_left`, suppose $y \in S_0 \cup S_1 \cup S_2$ and $y \in S_3$, so $A(y, v)$. If $y \in S_0$, then $y = v$, contradicting the absence of directed loops (`hA_loop`). If $y \in S_1$, then $E.\mathrm{Adj}(v, y)$, which by symmetry gives $E.\mathrm{Adj}(y, v)$, contradicting $A(y, v)$ by edge exclusivity (`hEA`). If $y \in S_2$, then $A(v, y)$, which contradicts $A(y, v)$ by the asymmetry of directed edges (`hA_asymm`).
uses
Set.disjoint_lefthave d03 : Disjoint (S0 ∪ S1 ∪ S2) S3 := by rw [Set.disjoint_left] intro y hy1 hy2 rcases hy1 with (rfl | hy1) | hy1 · exact hA_loop hy2 · exact hEA y v hy1.symm hy2 · exact hA_asymm y v hy2 hy1
The union $S_0 \cup S_1 \cup S_2 \cup S_3$ has cardinality $1 + r + z + z$.
Because each set is disjoint from the union of the preceding ones, `Set.ncard_union_eq` applies at each stage. First, $|S_0 \cup S_1| = |S_0| + |S_1| = 1 + r$, using `Set.ncard_singleton` and regularity (`hr1`). Next, $|S_0 \cup S_1 \cup S_2| = (1 + r) + z$ by regularity (`hr2`). Finally, $|S_0 \cup S_1 \cup S_2 \cup S_3| = (1 + r + z) + z$ by regularity (`hr3`).
uses
Set.ncard_union_eq,Set.ncard_singletonhave u1 : (S0 ∪ S1).ncard = 1 + r := by rw [Set.ncard_union_eq d01, Set.ncard_singleton, hr1] have u2 : (S0 ∪ S1 ∪ S2).ncard = 1 + r + z := by rw [Set.ncard_union_eq d02, u1, hr2] have u3 : (S0 ∪ S1 ∪ S2 ∪ S3).ncard = 1 + r + z + z := by rw [Set.ncard_union_eq d03, u2, hr3]
The cardinality of $S_0 \cup S_1 \cup S_2 \cup S_3$ is at most $|V|$.
Rewriting `Fintype.card V` into `Nat.card V` via `Nat.card_eq_fintype_card`, `Set.ncard_le_card` establishes that any subset of a finite type has cardinality at most the cardinality of the type itself.
uses
Nat.card_eq_fintype_card,Set.ncard_le_cardhave h_le : (S0 ∪ S1 ∪ S2 ∪ S3).ncard ≤ Fintype.card V := by rw [← Nat.card_eq_fintype_card] exact Set.ncard_le_card _
$r + 2z + 1 \le |V|$.
Linear integer arithmetic (`omega`) concludes the inequality $r + 2z + 1 \le |V|$ from the cardinality equality $|S_0 \cup S_1 \cup S_2 \cup S_3| = 1 + r + z + z$ and the subset bound $|S_0 \cup S_1 \cup S_2 \cup S_3| \le |V|$.
omega
Set.disjoint_left- Two sets are disjoint if and only if no element of the first set belongs to the second set.
Set.ncard_union_eq- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Set.ncard_singleton- A singleton set has cardinality 1.
Nat.card_eq_fintype_card- For a finite type, the general cardinality `Nat.card` equals the finite type cardinality `Fintype.card`.
Set.ncard_le_card- The cardinality of any subset of a finite type is at most the cardinality of the type itself.
- Because $V$ is a finite type, finiteness conditions required by set cardinality lemmas (such as `Set.ncard_union_eq`) are discharged automatically by Lean's typeclass synthesis and default tactics.
- The proof converts between set cardinality (`Set.ncard`) and type cardinality (`Fintype.card`) through the intermediate form `Nat.card`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem mixed_graph_card_ge_of_is_regular {V : Type*} [Fintype V] [Nonempty V] (E : SimpleGraph V) (A : V → V → Prop) (r z : ℕ) (hv : mixed_graph_is_valid E A) (hr : mixed_graph_is_regular E A r z) : r + 2 * z + 1 ≤ Fintype.card V := by inhabit V let v : V := default have hE_loop : ¬E.Adj v v := E.irrefl have hA_loop : ¬A v v := hv.1 v have hA_asymm : ∀ x y, A x y → ¬A y x := hv.2.1 have hEA : ∀ x y, E.Adj x y → ¬A x y := hv.2.2 obtain ⟨hr1, hr2, hr3⟩ := hr v let S0 : Set V := {v} let S1 : Set V := {y | E.Adj v y} let S2 : Set V := {y | A v y} let S3 : Set V := {y | A y v} have d01 : Disjoint S0 S1 := by rw [Set.disjoint_left] intro y hy1 hy2 cases hy1 exact hE_loop hy2 have d02 : Disjoint (S0 ∪ S1) S2 := by rw [Set.disjoint_left] intro y hy1 hy2 rcases hy1 with rfl | hy1 · exact hA_loop hy2 · exact hEA v y hy1 hy2 have d03 : Disjoint (S0 ∪ S1 ∪ S2) S3 := by rw [Set.disjoint_left] intro y hy1 hy2 rcases hy1 with (rfl | hy1) | hy1 · exact hA_loop hy2 · exact hEA y v hy1.symm hy2 · exact hA_asymm y v hy2 hy1 have u1 : (S0 ∪ S1).ncard = 1 + r := by rw [Set.ncard_union_eq d01, Set.ncard_singleton, hr1] have u2 : (S0 ∪ S1 ∪ S2).ncard = 1 + r + z := by rw [Set.ncard_union_eq d02, u1, hr2] have u3 : (S0 ∪ S1 ∪ S2 ∪ S3).ncard = 1 + r + z + z := by rw [Set.ncard_union_eq d03, u2, hr3] have h_le : (S0 ∪ S1 ∪ S2 ∪ S3).ncard ≤ Fintype.card V := by rw [← Nat.card_eq_fintype_card] exact Set.ncard_le_card _ omega