AFTD Auto-Formalizing Theoretical Domains

mixed_graph_card_ge_of_is_regular

theoremverifiedformalization

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

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|.

  1. 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)\}$.

    lines 4–14

      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}
  2. $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`).

    lines 16–20

    uses Set.disjoint_left

      have d01 : Disjoint S0 S1 := by
        rw [Set.disjoint_left]
        intro y hy1 hy2
        cases hy1
        exact hE_loop hy2
  3. $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`).

    lines 22–27

    uses Set.disjoint_left

      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
  4. $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`).

    lines 29–35

    uses Set.disjoint_left

      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
  5. 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`).

    lines 37–44

    uses Set.ncard_union_eq, Set.ncard_singleton

      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]
  6. 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.

    lines 46–48

    uses Nat.card_eq_fintype_card, Set.ncard_le_card

      have h_le : (S0 ∪ S1 ∪ S2 ∪ S3).ncard ≤ Fintype.card V := by
        rw [← Nat.card_eq_fintype_card]
        exact Set.ncard_le_card _
  7. $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|$.

    line 50

      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.

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

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
See it in the graphDiscuss this resultChallenge it