bipartite_complement_regular
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
- three_token_k2n_domination_number_four_geThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at least 4.
- Used by 1
- bipartite_complement_adj_spectrum_and_lambda2Let H be an s-regular bipartite simple graph whose two parts V and W each have size m ≥ 2, and let G = K_{V,W} \ E(H) be its bipartite…
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.
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).
uses
SimpleGraph.neighborFinset_sdiff,Finset.card_sdiff_of_subsetclassical intro v change ((completeBipartiteGraph V W \ H).neighborFinset v).card = m - s rw [SimpleGraph.neighborFinset_sdiff] rw [Finset.card_sdiff_of_subset]
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.
· have hH_card : (H.neighborFinset v).card = s := by have : H.degree v = s := hH_reg v exact this rw [hH_card]
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.
uses
SimpleGraph.mem_neighborFinset,completeBipartiteGraph_adj,Finset.card_image_of_injective,Sum.inr_injective,Finset.card_univrcases 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]
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.
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]
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).
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
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.
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