AFTD Auto-Formalizing Theoretical Domains

subcubic_isAcyclic_exists_independent_bipartite_component_partition

theoremverified

Every finite simple graph with maximum degree at most 3 that is acyclic 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 subcubic_isAcyclic_exists_independent_bipartite_component_partition
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
    (hdeg : G.maxDegree ≤ 3) (hforest : G.IsAcyclic) :
    ∃ 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. Assume that the maximum degree of G is at most 3 (hdeg : G.maxDegree ≤ 3) and that G is acyclic (hforest : G.IsAcyclic). Then there exists a finite subset of vertices L : Finset V such that: (1) the induced subgraph on L has no edges (G.induce (L : Set V) = ⊥, i.e., L is an independent set); (2) the induced subgraph on the complement Lᶜ is bipartite; and (3) for every connected component C of G[Lᶜ] and every vertex v ∈ L, the induced subgraph on the image of C in V united 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 theorem is proved by choosing the independent set L to be the empty set ∅. The induced subgraph G[∅] is trivially empty, its complement is the entire acyclic graph G which is bipartite as a forest, and the bipartite extension condition holds vacuously since no vertices belong to ∅.

  1. The empty set L = ∅ is chosen as the independent set candidate.

    We instantiate the existential quantifier by taking L = ∅. This produces three subgoals: showing that the induced subgraph G[∅] is empty (edgeless), that G[∅ᶜ] is bipartite, and that the bipartite extension property holds for every component and every vertex in L.

    line 11

      refine ⟨∅, ?_, ?_, ?_⟩
  2. The induced subgraph on the empty set has no edges (G[∅] = ⊥).

    By extensionality on adjacency, an edge would have to connect vertices in the empty set. A vertex in this induced subgraph comes with the hypothesis that it belongs to ∅, which simplifies to False.

    lines 12–13

      · ext ⟨x, hx⟩
        simp at hx
  3. The induced subgraph G[∅ᶜ] is bipartite.

    Because G is acyclic, any induced subgraph of G is acyclic. An acyclic graph has no cycles, hence no odd cycles, and is therefore bipartite (by `isBipartite`).

    line 14

    uses isBipartite

      · exact (hforest.induce _).isBipartite
  4. The component-extension condition holds vacuously.

    For any connected component C and vertex v ∈ L = ∅, the assumption that v belongs to the empty set simplifies to a contradiction, establishing the condition vacuously.

    lines 15–16

      · intro C v hv
        simp at hv
isBipartite
Every acyclic simple graph (forest) is bipartite.

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 acyclic subcubic simple graph admits an independent-bipartite component partition. -/theorem subcubic_isAcyclic_exists_independent_bipartite_component_partition    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (hdeg : G.maxDegree ≤ 3) (hforest : G.IsAcyclic) :    ∃ 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 (hforest.induce _).isBipartite  · intro C v hv    simp at hv
See it in the graphDiscuss this resultChallenge it