AFTD Auto-Formalizing Theoretical Domains

bipartite_complement_regular

theoremverified

Let H be an s-regular bipartite simple graph on parts V and W of size m. Then its bipartite complement K_{V,W} \ H is (m - s)-regular.

Statement

open scoped Classical in
theorem bipartite_complement_regular
    {V W : Type*} [Fintype V] [Fintype W]
    (m s : ℕ) (hV : Fintype.card V = m) (hW : Fintype.card W = m)
    (H : SimpleGraph (V ⊕ W)) (hH_sub : H ≤ completeBipartiteGraph V W)
    (hH_reg : H.IsRegularOfDegree s) :
    (completeBipartiteGraph V W \ H).IsRegularOfDegree (m - s)
Source
arXiv:2611.00591 Lemma 4.1
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

Read back from the Lean

Let $V$ and $W$ be finite types, and let $m, s \in \mathbb{N}$ such that $|V| = m$ and $|W| = m$. Let $H$ be a simple graph on the vertex set $V \oplus W$ that is a subgraph of the complete bipartite graph $\operatorname{completeBipartiteGraph} V\ W$ ($H \le \operatorname{completeBipartiteGraph} V\ W$). If $H$ is $s$-regular (every vertex in $V \oplus W$ has degree $s$ in $H$), then the bipartite complement $\operatorname{completeBipartiteGraph} V\ W \setminus H$ is $(m - s)$-regular (every vertex in $V \oplus W$ has degree $m - s$ in the difference graph).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that the bipartite complement K_{V,W} \ H is (m - s)-regular, we calculate the degree of an arbitrary vertex v. Since H is a subgraph of K_{V,W}, the neighborhood of v in the complement is the set difference N_{K_{V,W}}(v) \ N_H(v), whose cardinality is |N_{K_{V,W}}(v)| - |N_H(v)|. The term |N_H(v)| equals s by the s-regularity of H, and |N_{K_{V,W}}(v)| equals m because in the complete bipartite graph, every vertex in V is connected to all m vertices in W, and vice versa.

  1. To show K_{V,W} \\ H is (m - s)-regular, it suffices to show that for any vertex v, |N_{K_{V,W}}(v)| - |N_H(v)| = m - s, provided N_H(v) ⊆ N_{K_{V,W}}(v).

    By definition, a graph is (m - s)-regular if every vertex v has degree m - s, which means its neighbor finset has cardinality m - s. In a difference of graphs, the neighborhood of v is the set difference of its neighborhoods in the two graphs (SimpleGraph.neighborFinset_sdiff). Since the cardinality of a set difference t \\ s with s ⊆ t is |t| - |s| (Finset.card_sdiff_of_subset), this reduces the goal to showing |N_{K_{V,W}}(v)| - |N_H(v)| = m - s and verifying the subset inclusion N_H(v) ⊆ N_{K_{V,W}}(v).

    lines 9–13

    uses SimpleGraph.neighborFinset_sdiff, Finset.card_sdiff_of_subset

      classical
      intro v
      change ((completeBipartiteGraph V W \ H).neighborFinset v).card = m - s
      rw [SimpleGraph.neighborFinset_sdiff]
      rw [Finset.card_sdiff_of_subset]
  2. The neighborhood of v in H has size s, reducing the equation to |N_{K_{V,W}}(v)| - s = m - s.

    Because H is s-regular by assumption (hH_reg), the degree of v in H, which is the cardinality of its neighbor finset N_H(v), equals s. Substituting this leaves |N_{K_{V,W}}(v)| - s = m - s.

    lines 14–17

      · have hH_card : (H.neighborFinset v).card = s := by
          have : H.degree v = s := hH_reg v
          exact this
        rw [hH_card]
  3. When v ∈ V, the neighborhood of v in K_{V,W} has size m, completing the first case.

    We split into cases depending on whether v lies in V or W (rcases v with x | y). When v = Sum.inl x for x ∈ V, its neighbors in the complete bipartite graph are precisely the vertices of W, embedded as the image of W under Sum.inr (SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj). Since Sum.inr is injective (Sum.inr_injective), the size of this image is the cardinality of W (Finset.card_image_of_injective, Finset.card_univ), which is m by hypothesis hW. Substituting m yields m - s = m - s.

    lines 18–25

    uses SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj, Finset.card_image_of_injective, Sum.inr_injective, Finset.card_univ

        rcases v with x | y
        · have hdeg : ((completeBipartiteGraph V W).neighborFinset (Sum.inl x)).card = m := by
            have h : (completeBipartiteGraph V W).neighborFinset (Sum.inl x) = Finset.univ.image Sum.inr := by
              ext (a | b)
              · simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj]
              · simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj]
            rw [h, Finset.card_image_of_injective _ Sum.inr_injective, Finset.card_univ, hW]
          rw [hdeg]
  4. When v ∈ W, the neighborhood of v in K_{V,W} has size m, completing the second case.

    Symmetrically, when v = Sum.inr y for y ∈ W, its neighbors in K_{V,W} are precisely the vertices of V, embedded as the image of V under Sum.inl (SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj). Since Sum.inl is injective (Sum.inl_injective), this neighborhood has cardinality |V| = m (Finset.card_image_of_injective, Finset.card_univ, hV). Substituting m again yields m - s = m - s.

    lines 26–32

    uses SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj, Finset.card_image_of_injective, Sum.inl_injective, Finset.card_univ

        · have hdeg : ((completeBipartiteGraph V W).neighborFinset (Sum.inr y)).card = m := by
            have h : (completeBipartiteGraph V W).neighborFinset (Sum.inr y) = Finset.univ.image Sum.inl := by
              ext (a | b)
              · simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj]
              · simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj]
            rw [h, Finset.card_image_of_injective _ Sum.inl_injective, Finset.card_univ, hV]
          rw [hdeg]
  5. The neighborhood of v in H is a subset of its neighborhood in K_{V,W}.

    This discharges the side condition for Finset.card_sdiff_of_subset. If x ∈ N_H(v), then x is adjacent to v in H (SimpleGraph.mem_neighborFinset). Since H is a subgraph of K_{V,W} by hypothesis hH_sub, x and v are also adjacent in K_{V,W}, which means x ∈ N_{K_{V,W}}(v).

    lines 33–35

    uses SimpleGraph.mem_neighborFinset

      · intro x hx
        rw [SimpleGraph.mem_neighborFinset] at hx ⊢
        exact hH_sub hx
SimpleGraph.neighborFinset_sdiff
The neighbor finset of a vertex in a graph difference G₁ \\ G₂ is the difference of its neighbor finsets in G₁ and G₂.
Finset.card_sdiff_of_subset
If s ⊆ t are finite sets, then |t \\ s| = |t| - |s|.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
completeBipartiteGraph_adj
In the complete bipartite graph on V ⊕ W, two vertices are adjacent if and only if one is in V (via inl) and the other is in W (via inr).
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the original set.
Sum.inr_injective
The canonical inclusion map Sum.inr is injective.
Finset.card_univ
The universal finset of a finite type has cardinality equal to the cardinality of the type.
Sum.inl_injective
The canonical inclusion map Sum.inl is injective.

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

open scoped Classical in/-- The bipartite complement of an s-regular bipartite simple graph with parts of size m is (m - s)-regular. -/theorem bipartite_complement_regular    {V W : Type*} [Fintype V] [Fintype W]    (m s : ℕ) (hV : Fintype.card V = m) (hW : Fintype.card W = m)    (H : SimpleGraph (V ⊕ W)) (hH_sub : H ≤ completeBipartiteGraph V W)    (hH_reg : H.IsRegularOfDegree s) :    (completeBipartiteGraph V W \ H).IsRegularOfDegree (m - s) := by  classical  intro v  change ((completeBipartiteGraph V W \ H).neighborFinset v).card = m - s  rw [SimpleGraph.neighborFinset_sdiff]  rw [Finset.card_sdiff_of_subset]  · have hH_card : (H.neighborFinset v).card = s := by      have : H.degree v = s := hH_reg v      exact this    rw [hH_card]    rcases v with x | y    · have hdeg : ((completeBipartiteGraph V W).neighborFinset (Sum.inl x)).card = m := by        have h : (completeBipartiteGraph V W).neighborFinset (Sum.inl x) = Finset.univ.image Sum.inr := by          ext (a | b)          · simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj]          · simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj]        rw [h, Finset.card_image_of_injective _ Sum.inr_injective, Finset.card_univ, hW]      rw [hdeg]    · have hdeg : ((completeBipartiteGraph V W).neighborFinset (Sum.inr y)).card = m := by        have h : (completeBipartiteGraph V W).neighborFinset (Sum.inr y) = Finset.univ.image Sum.inl := by          ext (a | b)          · simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj]          · simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph_adj]        rw [h, Finset.card_image_of_injective _ Sum.inl_injective, Finset.card_univ, hV]      rw [hdeg]  · intro x hx    rw [SimpleGraph.mem_neighborFinset] at hx ⊢    exact hH_sub hx
See it in the graphDiscuss this resultChallenge it