subcubic_partition_component_le_three_of_isBipartite
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.
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.
uses
Subtype.mk.injEq,SimpleGraph.ComponentCompl.mem_supp_iff,SimpleGraph.ConnectedComponent.eq,SimpleGraph.reachable_bot,Subtype.ext_iff.mpconstructor 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
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.
rcases hbp with ⟨c⟩ let L : Finset V := Finset.filter (fun v => c v = 0) Finset.univ
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.
uses
SimpleGraph.induce_adj,SimpleGraph.bot_adj,iff_false,Finset.mem_filterhave 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
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.
uses
SimpleGraph.induce_adj,SimpleGraph.bot_adj,iff_false,Finset.mem_filter,Finset.mem_univhave 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
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.
uses
subcubic_partition_component_le_three_of_isBipartite_subsingleton,Fintype.card_le_one_iff_subsingleton.mprrefine ⟨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.
- While the theorem bounds the order of each connected component by 3, the argument actually proves the stronger bound that every component has order at most 1, since the complement of one color class in a 2-coloring is the other color class, which is also an independent set.
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.
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