subcubic_isAcyclic_exists_independent_bipartite_component_partition
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 ∅.
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.
refine ⟨∅, ?_, ?_, ?_⟩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.
· ext ⟨x, hx⟩ simp at hx
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`).
uses
isBipartite· exact (hforest.induce _).isBipartiteThe 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.
· intro C v hv simp at hv
isBipartite- Every acyclic simple graph (forest) is bipartite.
- The maximum degree bound `hdeg : G.maxDegree ≤ 3` is not used in the proof; choosing L = ∅ works for any acyclic graph.
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 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