AFTD Auto-Formalizing Theoretical Domains

subcubic_partition_component_le_three_of_isBipartite

theoremverified

Every bipartite finite simple graph admits a partition of its vertex set into an independent set L and a complement R = Lᶜ such that every connected component of the induced subgraph G[R] has order at most 3.

Statement

theorem subcubic_partition_component_le_three_of_isBipartite {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (hbp : G.IsBipartite) :
    ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧
      ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent,
        open scoped Classical in Fintype.card C ≤ 3
Source
arXiv:2611.05178 Section 5 -- Weighted Max Cut in Subcubic Graphs
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

Let V be a finite type with decidable equality, and let G be a simple graph on V. Assuming G is bipartite, there exists a finite subset L of V such that the subgraph induced by L has no edges (i.e., L is an independent set), and for every connected component C of the subgraph induced by the complement of L, the number of vertices in C is at most 3.

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

The proof partitions the vertex set using a proper 2-coloring c : V → {0, 1} guaranteed by the bipartiteness of G. The set L is defined as the color class c⁻¹(0), so its complement Lᶜ is the other color class c⁻¹(1). Because the coloring is proper, neither color class contains an edge, meaning both induced subgraphs G[L] and G[Lᶜ] are edgeless. A helper lemma shows that any connected component of an edgeless induced subgraph has at most one vertex, which immediately implies that every component of G[Lᶜ] has order at most 1, and hence at most 3.

  1. If the induced subgraph on the complement of K is edgeless, then every connected component of the complement is a subsingleton.

    To show that any component C has at most one vertex, consider two elements ⟨x, hx⟩ and ⟨y, hy⟩ of C. By SimpleGraph.ComponentCompl.mem_supp_iff, both x and y lie outside K and map to C under the canonical component projection. Since the induced subgraph on Kᶜ has no edges by hypothesis (h), reachability in G[Kᶜ] reduces to equality (SimpleGraph.reachable_bot), so the two vertices must have the same component if and only if they are equal (SimpleGraph.ConnectedComponent.eq). Hence ⟨x, hx⟩ = ⟨y, hy⟩, and extracting the underlying values (Subtype.ext_iff.mp) shows x = y.

    lines 5–16

    uses Subtype.mk.injEq, SimpleGraph.ComponentCompl.mem_supp_iff, SimpleGraph.ConnectedComponent.eq, SimpleGraph.reachable_bot, Subtype.ext_iff.mp

      constructor
      intro ⟨x, hx⟩ ⟨y, hy⟩
      rw [Subtype.mk.injEq]
      rw [SimpleGraph.ComponentCompl.mem_supp_iff] at hx hy
      rcases hx with ⟨hxK, hxC⟩
      rcases hy with ⟨hyK, hyC⟩
      have h_eq : G.componentComplMk hxK = G.componentComplMk hyK := by
        rw [hxC, hyC]
      change (G.induce Kᶜ).connectedComponentMk ⟨x, hxK⟩ = (G.induce Kᶜ).connectedComponentMk ⟨y, hyK⟩ at h_eq
      rw [h] at h_eq
      rw [SimpleGraph.ConnectedComponent.eq, SimpleGraph.reachable_bot] at h_eq
      exact Subtype.ext_iff.mp h_eq
  2. Obtain a 2-coloring from bipartiteness and define L as the subset of vertices of color 0.

    By definition of bipartiteness, G admits a proper 2-coloring c : V → Fin 2. We define L as the finset of all vertices v such that c(v) = 0.

    lines 24–25

      rcases hbp with ⟨c⟩
      let L : Finset V := Finset.filter (fun v => c v = 0) Finset.univ
  3. The induced subgraph on L has no edges, so L is an independent set.

    Suppose, for contradiction, that there were an edge between u, v ∈ L in G[L]. Then u and v are adjacent in G. By definition of L, both c(u) = 0 and c(v) = 0. However, because c is a proper coloring, adjacent vertices must receive distinct colors (c(u) ≠ c(v)), which yields 0 ≠ 0, a contradiction.

    lines 26–40

    uses SimpleGraph.induce_adj, SimpleGraph.bot_adj, iff_false, Finset.mem_filter

      have hL : G.induce (L : Set V) = ⊥ := by
        ext ⟨u, hu⟩ ⟨v, hv⟩
        simp only [SimpleGraph.induce_adj, SimpleGraph.bot_adj, iff_false]
        intro hadj
        have hu' : c u = 0 := by
          have : u ∈ L := hu
          rw [Finset.mem_filter] at this
          exact this.2
        have hv' : c v = 0 := by
          have : v ∈ L := hv
          rw [Finset.mem_filter] at this
          exact this.2
        have hne := c.valid hadj
        rw [hu', hv'] at hne
        exact hne rfl
  4. The induced subgraph on the complement Lᶜ has no edges, so Lᶜ is also an independent set.

    Suppose, for contradiction, that there were an edge between u, v ∈ Lᶜ in G[Lᶜ]. Since u ∉ L, c(u) ≠ 0, and since c takes values in Fin 2 = {0, 1}, it follows that c(u) = 1. By the same reasoning, c(v) = 1. But the properness of c requires c(u) ≠ c(v), giving 1 ≠ 1, a contradiction.

    lines 41–63

    uses SimpleGraph.induce_adj, SimpleGraph.bot_adj, iff_false, Finset.mem_filter, Finset.mem_univ

      have hR : G.induce (Lᶜ : Set V) = ⊥ := by
        ext ⟨u, hu⟩ ⟨v, hv⟩
        simp only [SimpleGraph.induce_adj, SimpleGraph.bot_adj, iff_false]
        intro hadj
        have hu' : c u = 1 := by
          have hu_not : u ∉ L := hu
          have : c u ≠ 0 := by
            intro h0
            apply hu_not
            rw [Finset.mem_filter]
            exact ⟨Finset.mem_univ u, h0⟩
          omega
        have hv' : c v = 1 := by
          have hv_not : v ∉ L := hv
          have : c v ≠ 0 := by
            intro h0
            apply hv_not
            rw [Finset.mem_filter]
            exact ⟨Finset.mem_univ v, h0⟩
          omega
        have hne := c.valid hadj
        rw [hu', hv'] at hne
        exact hne rfl
  5. Every connected component of G[Lᶜ] has order at most 3.

    We choose L as the required independent set. For any connected component C of G[Lᶜ], since G[Lᶜ] is edgeless, the helper lemma subcubic_partition_component_le_three_of_isBipartite_subsingleton shows that C is a subsingleton. A subsingleton has cardinality at most 1 (Fintype.card_le_one_iff_subsingleton.mpr), which is in particular at most 3.

    lines 64–68

    uses subcubic_partition_component_le_three_of_isBipartite_subsingleton, Fintype.card_le_one_iff_subsingleton.mpr

      refine ⟨L, hL, fun C => ?_⟩
      classical
      have : Subsingleton C := subcubic_partition_component_le_three_of_isBipartite_subsingleton G (L : Set V) hR C
      have : Fintype.card C ≤ 1 := Fintype.card_le_one_iff_subsingleton.mpr this
      omega
Fintype.card_le_one_iff_subsingleton.mpr
If a finite type has at most one element (is a subsingleton), then its cardinality is at most 1.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the filter predicate.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
iff_false
A proposition is logically equivalent to False if and only if its negation is true.
SimpleGraph.bot_adj
The edgeless graph has no edges between any pair of vertices.
SimpleGraph.ComponentCompl.mem_supp_iff
A vertex belongs to a connected component of the complement of K if and only if it does not belong to K and its component projection is that component.
SimpleGraph.ConnectedComponent.eq
Two vertices belong to the same connected component if and only if they are reachable from each other.
SimpleGraph.induce_adj
Two vertices in an induced subgraph are adjacent if and only if they are adjacent in the ambient graph.
SimpleGraph.reachable_bot
In the edgeless graph, two vertices are reachable from each other if and only if they are equal.
subcubic_partition_component_le_three_of_isBipartite_subsingleton
If the induced subgraph on the complement of K has no edges, then every connected component of the complement is a subsingleton (has at most one element).
Subtype.ext_iff.mp
If two subtype elements are equal, then their underlying values are equal.
Subtype.mk.injEq
Two subtype elements are equal if and only if their underlying values are equal.

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

lemma subcubic_partition_component_le_three_of_isBipartite_subsingleton {V : Type*}    (G : SimpleGraph V) (K : Set V) (h : G.induce Kᶜ = ⊥)    (C : G.ComponentCompl K) :    Subsingleton C := by  constructor  intro ⟨x, hx⟩ ⟨y, hy⟩  rw [Subtype.mk.injEq]  rw [SimpleGraph.ComponentCompl.mem_supp_iff] at hx hy  rcases hx with ⟨hxK, hxC⟩  rcases hy with ⟨hyK, hyC⟩  have h_eq : G.componentComplMk hxK = G.componentComplMk hyK := by    rw [hxC, hyC]  change (G.induce Kᶜ).connectedComponentMk ⟨x, hxK⟩ = (G.induce Kᶜ).connectedComponentMk ⟨y, hyK⟩ at h_eq  rw [h] at h_eq  rw [SimpleGraph.ConnectedComponent.eq, SimpleGraph.reachable_bot] at h_eq  exact Subtype.ext_iff.mp h_eq/-- Every bipartite graph admits an independent set whose complement has all connected components of order at most 3 (in fact order at most 1). -/theorem subcubic_partition_component_le_three_of_isBipartite {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (hbp : G.IsBipartite) :    ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧      ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent,        open scoped Classical in Fintype.card C ≤ 3 := by  rcases hbp with ⟨c⟩  let L : Finset V := Finset.filter (fun v => c v = 0) Finset.univ  have hL : G.induce (L : Set V) = ⊥ := by    ext ⟨u, hu⟩ ⟨v, hv⟩    simp only [SimpleGraph.induce_adj, SimpleGraph.bot_adj, iff_false]    intro hadj    have hu' : c u = 0 := by      have : u ∈ L := hu      rw [Finset.mem_filter] at this      exact this.2    have hv' : c v = 0 := by      have : v ∈ L := hv      rw [Finset.mem_filter] at this      exact this.2    have hne := c.valid hadj    rw [hu', hv'] at hne    exact hne rfl  have hR : G.induce (Lᶜ : Set V) = ⊥ := by    ext ⟨u, hu⟩ ⟨v, hv⟩    simp only [SimpleGraph.induce_adj, SimpleGraph.bot_adj, iff_false]    intro hadj    have hu' : c u = 1 := by      have hu_not : u ∉ L := hu      have : c u ≠ 0 := by        intro h0        apply hu_not        rw [Finset.mem_filter]        exact ⟨Finset.mem_univ u, h0⟩      omega    have hv' : c v = 1 := by      have hv_not : v ∉ L := hv      have : c v ≠ 0 := by        intro h0        apply hv_not        rw [Finset.mem_filter]        exact ⟨Finset.mem_univ v, h0⟩      omega    have hne := c.valid hadj    rw [hu', hv'] at hne    exact hne rfl  refine ⟨L, hL, fun C => ?_⟩  classical  have : Subsingleton C := subcubic_partition_component_le_three_of_isBipartite_subsingleton G (L : Set V) hR C  have : Fintype.card C ≤ 1 := Fintype.card_le_one_iff_subsingleton.mpr this  omega
See it in the graphDiscuss this resultChallenge it