triangle_free_subcubic_card_le_four_partition
Every finite simple graph on at most 4 vertices with maximum degree at most 3 that is triangle-free 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 triangle_free_subcubic_card_le_four_partition {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hdeg : G.maxDegree ≤ 3) (htf : G.CliqueFree 3) (hcard : Fintype.card V ≤ 4) : ∃ 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
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- triangle_free_card_le_four_isBipartiteEvery finite simple graph on at most 4 vertices that is triangle-free is bipartite (2-colorable).
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:
1. the maximum degree of $G$ is at most 3 (G.maxDegree ≤ 3),
2. $G$ is triangle-free / contains no 3-cliques (G.CliqueFree 3), and
3. the number of vertices in $V$ is at most 4 (Fintype.card V ≤ 4).
Then there exists a finite subset $L \subseteq V$ such that:
1. the subgraph of $G$ induced by $L$ has no edges (i.e., $L$ is an independent set, G.induce (L : Set V) = ⊥),
2. the subgraph of $G$ induced by the complement $L^c$ is bipartite ((G.induce (Lᶜ : Set V)).IsBipartite), and
3. for every connected component $C$ of the induced subgraph $G[L^c]$ and every vertex $v \in L$, the subgraph of $G$ induced by the vertices of $C$ along with $v$ is bipartite ((G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite).
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 requires finding an independent set L such that the complement subgraph G[Lᶜ] is bipartite and extending any component of G[Lᶜ] by any vertex in L remains bipartite. The proof simply chooses L = ∅, which is trivially an independent set and satisfies the component-extension condition vacuously. The remaining goal, that G[Lᶜ] = G[V] is bipartite, then follows from the fact that any triangle-free simple graph on at most 4 vertices is bipartite.
Choosing L = ∅ reduces the theorem to verifying three conditions: the induced subgraph on ∅ is empty, the induced subgraph on ∅ᶜ is bipartite, and the component-extension condition holds.
We instantiate the existential quantifier with the empty finset L = ∅. This produces three subgoals: showing that the induced subgraph on ∅ is the empty graph ⊥ (i.e. L is an independent set), showing that the induced subgraph on the complement ∅ᶜ is bipartite, and showing that every component of the complement graph remains bipartite when joined with any vertex in L.
refine ⟨∅, ?_, ?_, ?_⟩The induced subgraph on L = ∅ is the empty graph ⊥.
Coercing the empty finset to a set yields the empty set ∅ (lines 13–14). By Set.isEmpty_coe_sort, the subtype of elements in ∅ is an empty type (line 15). Since simple graphs on an empty type form a subsingleton, Subsingleton.elim proves that the induced subgraph on ∅ is equal to the empty graph ⊥ (line 16).
uses
Set.isEmpty_coe_sort,Subsingleton.elim· have hset0 : ((∅ : Finset V) : Set V) = (∅ : Set V) := by simp rw [hset0] haveI : IsEmpty ↥(∅ : Set V) := by rw [Set.isEmpty_coe_sort] exact Subsingleton.elim _ _
The induced subgraph on the complement Lᶜ = V is bipartite.
Because G is a triangle-free graph on at most 4 vertices, a prior theorem (triangle_free_card_le_four_isBipartite) shows that G itself is bipartite (line 17). The complement of the empty set is the universal set Set.univ (lines 18–19). By definition, the induced subgraph on Set.univ is the pullback graph along the subtype inclusion embedding (lines 20–21). Using SimpleGraph.Colorable.of_hom along the canonical homomorphism SimpleGraph.Hom.comap, the bipartiteness (2-colorability) of G pulls back to the induced subgraph on Set.univ (lines 22–23).
uses
triangle_free_card_le_four_isBipartite,SimpleGraph.Colorable.of_hom,SimpleGraph.Hom.comap· have hb : G.IsBipartite := triangle_free_card_le_four_isBipartite G htf hcard have hset : ((∅ : Finset V)ᶜ : Set V) = Set.univ := by simp rw [hset] rw [show G.induce (Set.univ : Set V) = G.comap (Function.Embedding.subtype (· ∈ (Set.univ : Set V))) from rfl] exact SimpleGraph.Colorable.of_hom (SimpleGraph.Hom.comap (Function.Embedding.subtype (· ∈ (Set.univ : Set V))) G) hb
For every connected component C of G[Lᶜ] and every vertex v ∈ L, the induced subgraph on V(C) ∪ {v} is bipartite.
We introduce a connected component C, a vertex v, and the hypothesis hv that v ∈ ∅ (line 24). Simplifying this hypothesis reveals a contradiction, as the empty set has no members, which closes the goal vacuously (line 25).
· intro C v hv simp at hv
Set.isEmpty_coe_sort- A set's coerced subtype is empty if and only if the set is empty.
Subsingleton.elim- Any two terms of a subsingleton type (a type with at most one term) are equal.
triangle_free_card_le_four_isBipartite- Every finite triangle-free simple graph on at most 4 vertices is bipartite.
SimpleGraph.Colorable.of_hom- A graph homomorphism from G to G' pulls an n-coloring of G' back to an n-coloring of G; in particular, if G' is bipartite (2-colorable), then so is G.
SimpleGraph.Hom.comap- For any vertex map f, the canonical map from the pullback graph comap f G to G is a graph homomorphism.
- In Lean, the induced subgraph on the universal set G[Set.univ] is formally represented as a pullback graph (comap) along the subtype inclusion embedding rather than being syntactically identical to G. Consequently, bipartiteness must be transferred from G to G[Set.univ] via a graph homomorphism.
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 triangle-free subcubic simple graph on at most 4 vertices admits an independent-bipartite component partition. -/theorem triangle_free_subcubic_card_le_four_partition {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hdeg : G.maxDegree ≤ 3) (htf : G.CliqueFree 3) (hcard : Fintype.card V ≤ 4) : ∃ 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 ⟨∅, ?_, ?_, ?_⟩ · have hset0 : ((∅ : Finset V) : Set V) = (∅ : Set V) := by simp rw [hset0] haveI : IsEmpty ↥(∅ : Set V) := by rw [Set.isEmpty_coe_sort] exact Subsingleton.elim _ _ · have hb : G.IsBipartite := triangle_free_card_le_four_isBipartite G htf hcard have hset : ((∅ : Finset V)ᶜ : Set V) = Set.univ := by simp rw [hset] rw [show G.induce (Set.univ : Set V) = G.comap (Function.Embedding.subtype (· ∈ (Set.univ : Set V))) from rfl] exact SimpleGraph.Colorable.of_hom (SimpleGraph.Hom.comap (Function.Embedding.subtype (· ∈ (Set.univ : Set V))) G) hb · intro C v hv simp at hv