bipartite_complement_connected
Let H be an s-regular bipartite simple graph on parts V and W of size m ≥ 2. If 2s < m, then the bipartite complement G = K_{V,W} \ E(H) is connected.
Statement
open scoped Classical in theorem bipartite_complement_connected {V W : Type*} [Fintype V] [Fintype W] (m s : ℕ) (hm : 2 ≤ m) (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) (hs : 2 * s < m) : (completeBipartiteGraph V W \ H).Connected
- Source
- step towards bipartite_complement_regular_spectrum_and_lambda2
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Arena.Reachable.transReachability is transitive.
- 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…
The proof, explained
To prove that the bipartite complement G = K_{V,W} \ H is connected, it suffices to show that all vertices can reach a fixed basepoint v₀ ∈ V. Because H is an s-regular bipartite graph, each vertex in V has s neighbours in W, and each vertex in W has s neighbours in V. Given two vertices in V, the union of their neighbourhoods in W has cardinality at most 2s < m = |W|, so by the pigeonhole principle they share a common non-neighbour in W, providing a two-edge path between them in G. Similarly, each vertex in W has a non-neighbour in V and is thus adjacent to V in G, connecting the entire graph through v₀.
The graph H has no edges with both endpoints in V or both endpoints in W.
Because H is a subgraph of the complete bipartite graph K_{V,W} (hypothesis hH_sub), any edge of H must connect an element of V to an element of W. Thus, an edge between two vertices in V, or between two vertices in W, contradicts the definition of K_{V,W}.
have hnl : ∀ v v', ¬ H.Adj (Sum.inl v) (Sum.inl v') := by intro v v' h have := hH_sub h simp at this have hnr : ∀ w w', ¬ H.Adj (Sum.inr w) (Sum.inr w') := by intro w w' h have := hH_sub h simp at this
Every row sum of the adjacency matrix of H equals s.
Because H is regular of degree s (hypothesis hH_reg), multiplying its adjacency matrix by the constant vector 1 yields s times 1 by SimpleGraph.adjMatrix_mulVec_const_apply_of_regular. Unfolding the matrix-vector product into a sum of matrix entries shows that the row sum at every vertex is s.
uses
SimpleGraph.adjMatrix_mulVec_const_apply_of_regularhave hrow : ∀ i, ∑ j, H.adjMatrix ℝ i j = s := by intro i have := SimpleGraph.adjMatrix_mulVec_const_apply_of_regular (α := ℝ) hH_reg (a := 1) (v := i) simp only [Matrix.mulVec, dotProduct, Function.const_apply, mul_one] at this exact this
Each vertex in V has degree s into W, and each vertex in W has degree s into V.
For any v ∈ V, the row sum of the adjacency matrix over V ⊕ W splits into a sum over V and a sum over W using Fintype.sum_sum_type. Because H has no edges within V, the first sum is 0. By SimpleGraph.adjMatrix_apply and Finset.sum_boole, the second sum counts the neighbours of v in W, which therefore equals s. An identical split for w ∈ W shows that w has degree s into V.
uses
Fintype.sum_sum_type,SimpleGraph.adjMatrix_apply,Finset.sum_boolehave hcardL : ∀ v, (Finset.univ.filter fun w => H.Adj (Sum.inl v) (Sum.inr w)).card = s := by intro v have h := hrow (Sum.inl v) rw [Fintype.sum_sum_type] at h simp only [SimpleGraph.adjMatrix_apply, hnl, if_false, Finset.sum_const_zero, zero_add, Finset.sum_boole] at h exact_mod_cast h have hcardR : ∀ w, (Finset.univ.filter fun v => H.Adj (Sum.inr w) (Sum.inl v)).card = s := by intro w have h := hrow (Sum.inr w) rw [Fintype.sum_sum_type] at h simp only [SimpleGraph.adjMatrix_apply, hnr, if_false, Finset.sum_const_zero, add_zero, Finset.sum_boole] at h exact_mod_cast h
Any cross-part pair not adjacent in H is adjacent in the complement G = K_{V,W} \ H.
By SimpleGraph.sdiff_adj, two vertices are adjacent in G if and only if they are adjacent in K_{V,W} and not adjacent in H. Since every pair (v, w) with v ∈ V and w ∈ W forms an edge of K_{V,W}, non-adjacency in H implies adjacency in G.
uses
SimpleGraph.sdiff_adjset G := completeBipartiteGraph V W \ H with hG have hGlr : ∀ v w, ¬ H.Adj (Sum.inl v) (Sum.inr w) → G.Adj (Sum.inl v) (Sum.inr w) := by intro v w h simp [hG, SimpleGraph.sdiff_adj, h]
Any two vertices in V are reachable from each other in G.
Let v, v' ∈ V. In H, the neighbours of v and v' in W each form sets of size s. By Finset.card_union_le, their union has size at most s + s = 2s. Because 2s < m = |W| (hs and Finset.card_univ), the union has strictly smaller cardinality than W, so by Finset.exists_mem_notMem_of_card_lt_card there exists some w ∈ W not adjacent in H to either v or v'. In G, w is adjacent to both v and v', providing a two-edge path v — w — v' between them.
uses
lt_of_le_of_lt,Finset.card_union_le,Finset.card_univ,Finset.exists_mem_notMem_of_card_lt_card-- two left vertices are joined through a common non-neighbour have hLL : ∀ v v', G.Reachable (Sum.inl v) (Sum.inl v') := by intro v v' have hlt : ((Finset.univ.filter fun w => H.Adj (Sum.inl v) (Sum.inr w)) ∪ (Finset.univ.filter fun w => H.Adj (Sum.inl v') (Sum.inr w))).card < (Finset.univ : Finset W).card := by refine lt_of_le_of_lt (Finset.card_union_le _ _) ?_ rw [hcardL, hcardL, Finset.card_univ, hW] omega obtain ⟨w, -, hw⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, not_or] at hw exact (hGlr v w hw.1).reachable.trans (hGlr v' w hw.2).reachable.symm
Every vertex in W is adjacent in G to at least one vertex in V.
For any w ∈ W, its neighbourhood in V has size s in H. Because 2s < m and s ≥ 0, we have s < m = |V|. By Finset.exists_mem_notMem_of_card_lt_card, there is some v ∈ V not adjacent to w in H, which means v and w are adjacent in G.
uses
Finset.card_univ,Finset.exists_mem_notMem_of_card_lt_cardhave hR : ∀ w, ∃ v, G.Adj (Sum.inl v) (Sum.inr w) := by intro w have hlt : (Finset.univ.filter fun v => H.Adj (Sum.inr w) (Sum.inl v)).card < (Finset.univ : Finset V).card := by rw [hcardR, Finset.card_univ, hV]; omega obtain ⟨v, -, hv⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv exact ⟨v, hGlr v w (fun h => hv h.symm)⟩
Every vertex in G is reachable from a fixed base vertex v₀ ∈ V.
Since |V| = m ≥ 2 > 0, V is nonempty by Fintype.card_pos_iff, allowing us to fix a basepoint v₀ ∈ V. For any vertex x of G, if x = v ∈ V, it is reachable from v₀ by the two-edge path property. If x = w ∈ W, w is adjacent in G to some v ∈ V, which in turn is reachable from v₀, so v₀ reaches w by transitivity.
uses
Fintype.card_pos_iffobtain ⟨v0⟩ : Nonempty V := by rw [← Fintype.card_pos_iff]; omega have hreach : ∀ x, G.Reachable (Sum.inl v0) x := by intro x rcases x with v | w · exact hLL v0 v · obtain ⟨v, hv⟩ := hR w exact (hLL v0 v).trans hv.reachable
The bipartite complement G is connected.
The vertex set V ⊕ W is nonempty since it contains v₀. Furthermore, any two vertices x and y in G are reachable from each other by routing through v₀ (using symmetry and transitivity of reachability), proving that G is connected.
haveI : Nonempty (V ⊕ W) := ⟨Sum.inl v0⟩ exact ⟨fun x y => (hreach x).symm.trans (hreach y)⟩
Fintype.sum_sum_type- The sum of a function over a disjoint sum type α₁ ⊕ α₂ equals the sum over α₁ plus the sum over α₂.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.exists_mem_notMem_of_card_lt_card- If a finite set s has strictly smaller cardinality than a finite set t, there exists an element of t not in s.
Finset.sum_boole- The sum of a boolean indicator over a finite set equals the cardinality of the subset satisfying the condition.
Fintype.card_pos_iff- A finite type has strictly positive cardinality if and only if it is nonempty.
lt_of_le_of_lt- If a ≤ b and b < c in a preorder, then a < c.
SimpleGraph.adjMatrix_apply- The (v, w) entry of the adjacency matrix is 1 if v and w are adjacent, and 0 otherwise.
SimpleGraph.adjMatrix_mulVec_const_apply_of_regular- For a d-regular graph G, multiplying its adjacency matrix by the constant vector with value a produces the constant vector with value d * a.
SimpleGraph.sdiff_adj- Two vertices are adjacent in the graph difference G₁ \ G₂ if and only if they are adjacent in G₁ and not adjacent in G₂.
- Regularity of H is formulated via its adjacency matrix over ℝ: multiplying by the constant-one vector shows that all row sums equal s, from which the degree into the other bipartition part is extracted.
- Mathlib's definition of SimpleGraph.Connected requires both preconnectedness (every pair of vertices is reachable) and an explicit Nonempty instance on the vertex type.
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/-- If H is an s-regular bipartite simple graph on parts V and W of size m ≥ 2 with 2s < m, then its bipartite complement K_{V,W} \ H is connected. -/theorem bipartite_complement_connected {V W : Type*} [Fintype V] [Fintype W] (m s : ℕ) (hm : 2 ≤ m) (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) (hs : 2 * s < m) : (completeBipartiteGraph V W \ H).Connected := by have hnl : ∀ v v', ¬ H.Adj (Sum.inl v) (Sum.inl v') := by intro v v' h have := hH_sub h simp at this have hnr : ∀ w w', ¬ H.Adj (Sum.inr w) (Sum.inr w') := by intro w w' h have := hH_sub h simp at this have hrow : ∀ i, ∑ j, H.adjMatrix ℝ i j = s := by intro i have := SimpleGraph.adjMatrix_mulVec_const_apply_of_regular (α := ℝ) hH_reg (a := 1) (v := i) simp only [Matrix.mulVec, dotProduct, Function.const_apply, mul_one] at this exact this have hcardL : ∀ v, (Finset.univ.filter fun w => H.Adj (Sum.inl v) (Sum.inr w)).card = s := by intro v have h := hrow (Sum.inl v) rw [Fintype.sum_sum_type] at h simp only [SimpleGraph.adjMatrix_apply, hnl, if_false, Finset.sum_const_zero, zero_add, Finset.sum_boole] at h exact_mod_cast h have hcardR : ∀ w, (Finset.univ.filter fun v => H.Adj (Sum.inr w) (Sum.inl v)).card = s := by intro w have h := hrow (Sum.inr w) rw [Fintype.sum_sum_type] at h simp only [SimpleGraph.adjMatrix_apply, hnr, if_false, Finset.sum_const_zero, add_zero, Finset.sum_boole] at h exact_mod_cast h set G := completeBipartiteGraph V W \ H with hG have hGlr : ∀ v w, ¬ H.Adj (Sum.inl v) (Sum.inr w) → G.Adj (Sum.inl v) (Sum.inr w) := by intro v w h simp [hG, SimpleGraph.sdiff_adj, h] -- two left vertices are joined through a common non-neighbour have hLL : ∀ v v', G.Reachable (Sum.inl v) (Sum.inl v') := by intro v v' have hlt : ((Finset.univ.filter fun w => H.Adj (Sum.inl v) (Sum.inr w)) ∪ (Finset.univ.filter fun w => H.Adj (Sum.inl v') (Sum.inr w))).card < (Finset.univ : Finset W).card := by refine lt_of_le_of_lt (Finset.card_union_le _ _) ?_ rw [hcardL, hcardL, Finset.card_univ, hW] omega obtain ⟨w, -, hw⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, not_or] at hw exact (hGlr v w hw.1).reachable.trans (hGlr v' w hw.2).reachable.symm have hR : ∀ w, ∃ v, G.Adj (Sum.inl v) (Sum.inr w) := by intro w have hlt : (Finset.univ.filter fun v => H.Adj (Sum.inr w) (Sum.inl v)).card < (Finset.univ : Finset V).card := by rw [hcardR, Finset.card_univ, hV]; omega obtain ⟨v, -, hv⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv exact ⟨v, hGlr v w (fun h => hv h.symm)⟩ obtain ⟨v0⟩ : Nonempty V := by rw [← Fintype.card_pos_iff]; omega have hreach : ∀ x, G.Reachable (Sum.inl v0) x := by intro x rcases x with v | w · exact hLL v0 v · obtain ⟨v, hv⟩ := hR w exact (hLL v0 v).trans hv.reachable haveI : Nonempty (V ⊕ W) := ⟨Sum.inl v0⟩ exact ⟨fun x y => (hreach x).symm.trans (hreach y)⟩