AFTD Auto-Formalizing Theoretical Domains

bipartite_exists_independent_bipartite_component_partition

theoremverified

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.

  1. 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 ∈ ∅.

    line 11

      refine ⟨∅, ?_, ?_, ?_⟩
  2. 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.

    lines 12–13

      · ext ⟨x, hx⟩
        simp at hx
  3. 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.

    line 14

    uses SimpleGraph.Colorable.of_hom

      · exact SimpleGraph.Colorable.of_hom ⟨Subtype.val, fun h => h⟩ hbip
  4. 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.

    lines 15–16

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

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

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