AFTD Auto-Formalizing Theoretical Domains

bipartite_complement_connected

theoremverified

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
Used by 1

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

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

    lines 10–17

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

    lines 18–22

    uses SimpleGraph.adjMatrix_mulVec_const_apply_of_regular

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

    lines 23–36

    uses Fintype.sum_sum_type, SimpleGraph.adjMatrix_apply, Finset.sum_boole

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

    lines 37–40

    uses SimpleGraph.sdiff_adj

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

    lines 41–52

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

    lines 53–60

    uses Finset.card_univ, Finset.exists_mem_notMem_of_card_lt_card

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

    lines 61–68

    uses Fintype.card_pos_iff

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

    lines 69–70

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

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