bipartite_exists_independent_bipartite_component_partition
Every finite bipartite simple graph admits a partition into an independent set L and complement R = Lᶜ such that G[R] is bipartite and for every connected component C of G[R] and every vertex v in L, the induced subgraph on V(C) ∪ {v} is bipartite.
Statement
theorem bipartite_exists_independent_bipartite_component_partition {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hbip : G.IsBipartite) : ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ (G.induce (Lᶜ : Set V)).IsBipartite ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, ∀ v ∈ L, (G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite
- Source
- scout/2611-05178-weighted-max-cut-in-subcubic-graphs.md:1025
- 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$ with decidable adjacency. If $G$ is bipartite, then there exists a finite subset $L \subseteq V$ such that: 1. The induced subgraph $G[L]$ has no edges (i.e., $L$ is an independent set); 2. The induced subgraph on the complement, $G[V \setminus L]$, is bipartite; and 3. For every connected component $C$ of $G[V \setminus L]$ and every vertex $v \in L$, the induced subgraph of $G$ on the vertices of $C$ together with $v$ is bipartite.
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 chooses the empty set L = ∅ as the independent set witness. With this choice, the induced subgraph G[L] is the empty graph ⊥, and its complement G[Lᶜ] inherits bipartiteness from G via the canonical inclusion homomorphism. The third condition, requiring that adding any vertex v ∈ L to a connected component of G[Lᶜ] preserves bipartiteness, is vacuously true because L contains no vertices.
It suffices to establish the three conditions for the candidate set L = ∅.
We choose the empty set ∅ as the witness for L. This decomposes the existential goal into three subgoals: showing that the induced subgraph G[∅] is the empty graph ⊥, showing that G[∅ᶜ] is bipartite, and verifying the bipartiteness of G[V(C) ∪ {v}] for every component C of G[∅ᶜ] and every vertex v ∈ ∅.
refine ⟨∅, ?_, ?_, ?_⟩The induced subgraph G[∅] is the empty graph ⊥.
By graph extensionality, we consider adjacency between arbitrary vertices of the induced subgraph G[∅]. Each such vertex is a subtype element ⟨x, hx⟩ where hx is the assertion that x ∈ ∅. Simplifying this membership hypothesis exposes a contradiction (x ∈ ∅ ↔ False), which closes the goal.
· ext ⟨x, hx⟩ simp at hx
The induced subgraph G[∅ᶜ] is bipartite.
Bipartiteness of a simple graph is defined as 2-colorability. The subtype projection Subtype.val defines an edge-preserving graph homomorphism from the induced subgraph G[∅ᶜ] to G. Applying SimpleGraph.Colorable.of_hom pulls back the 2-coloring of G (from hbip) to establish that G[∅ᶜ] is also bipartite.
uses
SimpleGraph.Colorable.of_hom· exact SimpleGraph.Colorable.of_hom ⟨Subtype.val, fun h => h⟩ hbip
For every connected component C of G[∅ᶜ] and every vertex v ∈ ∅, the subgraph induced on V(C) ∪ {v} is bipartite.
We introduce an arbitrary connected component C of G[∅ᶜ], an arbitrary vertex v, and the hypothesis hv that v ∈ ∅. Simplifying hv reveals that it is false, so the universal implication holds vacuously.
· intro C v hv simp at hv
SimpleGraph.Colorable.of_hom- A graph homomorphism from G to G' preserves n-colorability: if G' is n-colorable, then G is also n-colorable.
- The theorem statement does not require L to be non-empty or non-trivial; setting L = ∅ trivially satisfies all conditions without requiring any non-trivial graph-theoretic decomposition.
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.
/-- Every finite bipartite simple graph admits an independent-bipartite component partition. -/theorem bipartite_exists_independent_bipartite_component_partition {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hbip : G.IsBipartite) : ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ (G.induce (Lᶜ : Set V)).IsBipartite ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, ∀ v ∈ L, (G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite := by refine ⟨∅, ?_, ?_, ?_⟩ · ext ⟨x, hx⟩ simp at hx · exact SimpleGraph.Colorable.of_hom ⟨Subtype.val, fun h => h⟩ hbip · intro C v hv simp at hv