subcubic_odd_girth_five_partition_component_le_three_negation
It is not the case that every finite simple graph with maximum degree at most 3, clique-free of order 3, and not bipartite admits a partition of its vertex set into an independent set L and a complement R = Lᶜ such that every connected component of the induced subgraph G[R] has order at most 3.
Statement
theorem subcubic_odd_girth_five_partition_component_le_three_negation : ¬ (∀ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], G.maxDegree ≤ 3 → G.CliqueFree 3 → ¬G.IsBipartite → ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, open scoped Classical in Fintype.card C ≤ 3)
- Related work
- arXiv:2611.05178 Question 5.4 -- Weighted Max Cut in Subcubic Graphs
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- not_not_subcubic_odd_girth_five_partition_component_le_three_negationThe statement
not_subcubic_odd_girth_five_partition_component_le_three_negationis false: The statement is¬ (¬ (∀ ...)), which…
- not_not_subcubic_odd_girth_five_partition_component_le_three_negationThe statement
Read back from the Lean
The theorem asserts the negation of the following statement: for every finite type V (with decidable equality) and every simple graph G on V (with decidable adjacency), if G has maximum degree at most 3 (G.maxDegree ≤ 3), is triangle-free (G.CliqueFree 3), and is not bipartite (¬G.IsBipartite), then there exists a subset of vertices L : Finset V such that L is an independent set in G (the induced subgraph G.induce (L : Set V) has no edges, i.e., equals ⊥) and every connected component C of the induced subgraph on the complement V \ L has at most 3 vertices (Fintype.card C ≤ 3).
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 exhibiting the Wagner graph (the Möbius ladder M₈ on 8 vertices) as a counterexample. The Wagner graph is verified by finite exhaustive checking to have maximum degree at most 3, to be triangle-free, and to be non-bipartite. By exhaustive search, every independent set L in the Wagner graph has the property that some connected component of its induced complement graph has at least 4 vertices. Assuming for contradiction that the general statement holds, applying it to the Wagner graph yields an independent set whose complement components all have size at most 3, contradicting the existence of a component with at least 4 vertices.
Adjacency in the Wagner graph is decidable.
The relation defining adjacency on the 8 vertices is given by equality modulo 8; unfolding the graph definition and `SimpleGraph.fromRel` allows Lean's typeclass resolution to synthesize the decidability instance.
instance subcubic_odd_girth_five_partition_component_le_three_negation_wg_dec : DecidableRel subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.Adj := by unfold subcubic_odd_girth_five_partition_component_le_three_negation_wg SimpleGraph.fromRel infer_instance
The Wagner graph has maximum degree at most 3. automation
The maximum degree is verified by exhaustive computation (`decide`) over the 8 vertices of the graph, each having degree exactly 3.
theorem subcubic_odd_girth_five_partition_component_le_three_negation_wg_maxDegree : subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.maxDegree ≤ 3 := by decide
The Wagner graph is triangle-free (contains no 3-cliques). automation
Unfolding the definition of `CliqueFree 3` reduces the claim to verifying that no 3-subset forms a clique, which is checked by `decide`.
uses
SimpleGraph.CliqueFreetheorem subcubic_odd_girth_five_partition_component_le_three_negation_wg_cliqueFree : subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.CliqueFree 3 := by unfold SimpleGraph.CliqueFree decide
The Wagner graph is not bipartite.
A bipartite graph is 2-colorable. Assuming a 2-coloring exists, an exhaustive finite search (`decide`) proves that every map from the 8 vertices to 2 colors creates an adjacent monochromatic pair, contradicting proper coloring.
uses
SimpleGraph.IsBipartite,SimpleGraph.Colorabletheorem subcubic_odd_girth_five_partition_component_le_three_negation_wg_not_bipartite : ¬ subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.IsBipartite := by rw [SimpleGraph.IsBipartite, SimpleGraph.Colorable] rintro ⟨c⟩ have key : ∀ f : ULift.{u, 0} (Fin 8) → Fin 2, ∃ i j : ULift.{u, 0} (Fin 8), subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.Adj i j ∧ f i = f j := by decide obtain ⟨i, j, hij, heq⟩ := key c.toFun exact c.valid hij heq
For every independent set in the Wagner graph, some connected component of its complement has at least 4 vertices. automation
Exhaustive finite evaluation (`decide`) over all subsets of the 8 vertices checks that if a subset is independent, there is a vertex in its complement whose reachable set in the induced complement subgraph has cardinality at least 4.
theorem subcubic_odd_girth_five_partition_component_le_three_negation_wg_key : ∀ L : Finset (ULift.{u, 0} (Fin 8)), (∀ x ∈ L, ∀ y ∈ L, x ≠ y → ¬ subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.Adj x y) → ∃ v : ↥((↑L)ᶜ : Set (ULift.{u, 0} (Fin 8))), 4 ≤ (Finset.univ.filter (fun w => (SimpleGraph.induce (↑L)ᶜ subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}).Reachable v w)).card := by decide
All complement vertices reachable from v belong to the connected component C₀ containing v.
Let C₀ be the connected component of v in G[Kᶜ]. Any vertex w reachable from v in the complement-induced subgraph has the same connected component as v by `SimpleGraph.ConnectedComponent.sound`, so w belongs to C₀.
uses
SimpleGraph.ConnectedComponent.soundlemma subcubic_odd_girth_five_partition_component_le_three_negation_card_contra {V : Type u} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (K : Set V) (v : ↥(Kᶜ)) {S : Finset ↥(Kᶜ)} (hS : 4 ≤ S.card) (hSreach : ∀ w ∈ S, (G.induce Kᶜ).Reachable v w) (hcomp : ∀ C : G.ComponentCompl K, Nat.card C ≤ 3) : False := by classical let C₀ : G.ComponentCompl K := G.componentComplMk (v := v.val) v.prop have hC₀ : Nat.card C₀ ≤ 3 := hcomp C₀ have hmem : ∀ w ∈ S, (w.val : V) ∈ C₀ := by intro w hw have heq : G.componentComplMk (v := w.val) w.prop = C₀ := by simp only [C₀] unfold SimpleGraph.componentComplMk exact (SimpleGraph.ConnectedComponent.sound (hSreach w hw)).symm rw [← heq] exact G.componentComplMk_mem w.prop
A reachable subset of size at least 4 in G[Kᶜ] contradicts the hypothesis that every complement component has size at most 3.
The inclusion mapping elements of S into the component C₀ is injective by `Subtype.ext`, so |S| ≤ |C₀| by `Fintype.card_le_of_injective`. Combining |S| ≥ 4 with |C₀| ≤ 3 produces a contradiction via linear arithmetic (`omega`).
uses
Subtype.ext,Fintype.card_le_of_injective,Fintype.card_coe,Nat.card_eq_fintype_cardhave hinj : Function.Injective (fun w : ↥S => (⟨w.val.val, hmem w.val w.prop⟩ : {x : V // x ∈ C₀})) := by intro a b hab simp only [Subtype.mk.injEq] at hab exact Subtype.ext (Subtype.ext hab) have hle : Fintype.card ↥S ≤ Fintype.card {x : V // x ∈ C₀} := Fintype.card_le_of_injective _ hinj rw [Fintype.card_coe] at hle have hC₀' : Fintype.card {x : V // x ∈ C₀} ≤ 3 := by rw [← Nat.card_eq_fintype_card] exact hC₀ omega
Assuming the universal statement, the Wagner graph admits an independent set L whose complement components all have size at most 3.
Assume for contradiction that every finite subcubic triangle-free non-bipartite graph admits such an independent set. Specializing this hypothesis to the Wagner graph—using its verified properties that max degree is at most 3, it is triangle-free, and not bipartite—yields an independent set L such that every component of the complement graph has order at most 3.
uses
subcubic_odd_girth_five_partition_component_le_three_negation_wg_maxDegree,subcubic_odd_girth_five_partition_component_le_three_negation_wg_cliqueFree,subcubic_odd_girth_five_partition_component_le_three_negation_wg_not_bipartiteintro H classical obtain ⟨L, hind, hcomp⟩ := H subcubic_odd_girth_five_partition_component_le_three_negation_wg subcubic_odd_girth_five_partition_component_le_three_negation_wg_maxDegree subcubic_odd_girth_five_partition_component_le_three_negation_wg_cliqueFree subcubic_odd_girth_five_partition_component_le_three_negation_wg_not_bipartite
The subset L is an independent set (no two distinct vertices in L are adjacent).
Because the induced subgraph on L is the empty graph ⊥, any adjacency between distinct vertices in L would mean an edge in ⊥ by `SimpleGraph.induce_adj`, which is impossible by `SimpleGraph.bot_adj`.
uses
SimpleGraph.induce_adj,SimpleGraph.bot_adjhave hL : ∀ x ∈ L, ∀ y ∈ L, x ≠ y → ¬ subcubic_odd_girth_five_partition_component_le_three_negation_wg.Adj x y := by intro x hx y hy hxy hadj have hadj' : (subcubic_odd_girth_five_partition_component_le_three_negation_wg.induce (↑L)).Adj ⟨x, by simpa using hx⟩ ⟨y, by simpa using hy⟩ := by rwa [SimpleGraph.induce_adj] rw [hind] at hadj' exact (SimpleGraph.bot_adj _ _).mp hadj'
The independent set L leaves a complement vertex v with at least 4 reachable vertices, while all components have size at most 3.
Applying the Wagner graph key lemma to L yields a complement vertex v whose reachable set in G[Lᶜ] has size at least 4. The component size bound is converted from `Fintype.card` to `Nat.card`.
uses
subcubic_odd_girth_five_partition_component_le_three_negation_wg_key,Nat.card_eq_fintype_cardobtain ⟨v, hv⟩ := subcubic_odd_girth_five_partition_component_le_three_negation_wg_key L hL have hcomp' : ∀ C : subcubic_odd_girth_five_partition_component_le_three_negation_wg.ComponentCompl (↑L), Nat.card C ≤ 3 := by intro C rw [Nat.card_eq_fintype_card] exact hcomp C
A contradiction is reached, disproving the universal partition statement.
Applying the bridge lemma `card_contra` with the Wagner graph, the independent set L, and the set of vertices reachable from v in the complement-induced subgraph derives `False`.
uses
subcubic_odd_girth_five_partition_component_le_three_negation_card_contrarefine subcubic_odd_girth_five_partition_component_le_three_negation_card_contra subcubic_odd_girth_five_partition_component_le_three_negation_wg (↑L : Set _) v (S := Finset.univ.filter (fun w => (SimpleGraph.induce (↑L)ᶜ subcubic_odd_girth_five_partition_component_le_three_negation_wg).Reachable v w)) ?_ ?_ hcomp' · exact hv · intro w hw exact (Finset.mem_filter.mp hw).2
SimpleGraph.CliqueFree- A simple graph has no complete subgraph on n vertices.
SimpleGraph.IsBipartite- A simple graph is bipartite, meaning its vertices can be partitioned into two independent sets.
SimpleGraph.Colorable- A simple graph admits a proper vertex coloring using n colors.
SimpleGraph.ConnectedComponent.sound- If two vertices are reachable from each other, they belong to the same connected component.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Fintype.card_le_of_injective- An injective map between finite types implies the cardinality of the domain is at most the cardinality of the codomain.
Fintype.card_coe- The cardinality of a finite set coerced to a subtype is equal to its finset cardinality.
Nat.card_eq_fintype_card- The general cardinality `Nat.card` of a finite type coincides with its `Fintype.card`.
subcubic_odd_girth_five_partition_component_le_three_negation_wg_maxDegree- The maximum degree of the Wagner graph is at most 3.
subcubic_odd_girth_five_partition_component_le_three_negation_wg_cliqueFree- The Wagner graph is triangle-free (contains no 3-clique).
subcubic_odd_girth_five_partition_component_le_three_negation_wg_not_bipartite- The Wagner graph is not bipartite.
SimpleGraph.induce_adj- Two vertices are adjacent in an induced subgraph if and only if they are adjacent in the ambient graph.
SimpleGraph.bot_adj- The empty graph (bottom element `⊥`) has no edges.
subcubic_odd_girth_five_partition_component_le_three_negation_wg_key- For every independent set in the Wagner graph, some vertex in the complement can reach at least 4 vertices in the complement-induced subgraph.
subcubic_odd_girth_five_partition_component_le_three_negation_card_contra- In any graph, if a vertex in the complement of K can reach at least 4 complement vertices, not all connected components of the complement can have size at most 3.
- The properties of the Wagner graph (maximum degree at most 3, triangle-freeness, non-bipartiteness, and the property that every independent set leaves a complement component with at least 4 vertices) are verified mechanically by `decide` via exhaustive finite checking over the 8 vertices.
- The universe lifting `ULift (Fin 8)` is a formal artifact to allow the finite 8-vertex graph to be used in an arbitrary universe `u`.
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.
set_option maxHeartbeats 4000000universe u/-- The Wagner graph (Möbius ladder M8): on `ULift (Fin 8)`, vertex `i` is adjacentto `i+1` and to `i+4` (mod 8). It is cubic, triangle-free and not bipartite. -/def subcubic_odd_girth_five_partition_component_le_three_negation_wg : SimpleGraph (ULift.{u, 0} (Fin 8)) := SimpleGraph.fromRel fun i j => j.down = i.down + 1 ∨ j.down = i.down + 4instance subcubic_odd_girth_five_partition_component_le_three_negation_wg_dec : DecidableRel subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.Adj := by unfold subcubic_odd_girth_five_partition_component_le_three_negation_wg SimpleGraph.fromRel infer_instance/-- The Wagner graph has maximum degree at most 3. -/theorem subcubic_odd_girth_five_partition_component_le_three_negation_wg_maxDegree : subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.maxDegree ≤ 3 := by decide/-- The Wagner graph is triangle-free (clique-free of order 3). -/theorem subcubic_odd_girth_five_partition_component_le_three_negation_wg_cliqueFree : subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.CliqueFree 3 := by unfold SimpleGraph.CliqueFree decide/-- The Wagner graph is not bipartite (it contains an odd cycle). -/theorem subcubic_odd_girth_five_partition_component_le_three_negation_wg_not_bipartite : ¬ subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.IsBipartite := by rw [SimpleGraph.IsBipartite, SimpleGraph.Colorable] rintro ⟨c⟩ have key : ∀ f : ULift.{u, 0} (Fin 8) → Fin 2, ∃ i j : ULift.{u, 0} (Fin 8), subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.Adj i j ∧ f i = f j := by decide obtain ⟨i, j, hij, heq⟩ := key c.toFun exact c.valid hij heq/-- Key finite fact for the Wagner graph: for every independent vertex set `L`there is a vertex `v` of the complement whose connected component in the inducedcomplement graph has at least four vertices. -/theorem subcubic_odd_girth_five_partition_component_le_three_negation_wg_key : ∀ L : Finset (ULift.{u, 0} (Fin 8)), (∀ x ∈ L, ∀ y ∈ L, x ≠ y → ¬ subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}.Adj x y) → ∃ v : ↥((↑L)ᶜ : Set (ULift.{u, 0} (Fin 8))), 4 ≤ (Finset.univ.filter (fun w => (SimpleGraph.induce (↑L)ᶜ subcubic_odd_girth_five_partition_component_le_three_negation_wg.{u}).Reachable v w)).card := by decide/-- Bridge lemma: if some component of the complement-induced graph `G.induce Kᶜ`contains at least four vertices (witnessed by a Finset `S` of vertices reachablefrom `v`), then the hypothesis that every such component has at most threevertices fails. Stated with `Nat.card` so no `Classical` Fintype scope is needed. -/lemma subcubic_odd_girth_five_partition_component_le_three_negation_card_contra {V : Type u} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (K : Set V) (v : ↥(Kᶜ)) {S : Finset ↥(Kᶜ)} (hS : 4 ≤ S.card) (hSreach : ∀ w ∈ S, (G.induce Kᶜ).Reachable v w) (hcomp : ∀ C : G.ComponentCompl K, Nat.card C ≤ 3) : False := by classical let C₀ : G.ComponentCompl K := G.componentComplMk (v := v.val) v.prop have hC₀ : Nat.card C₀ ≤ 3 := hcomp C₀ have hmem : ∀ w ∈ S, (w.val : V) ∈ C₀ := by intro w hw have heq : G.componentComplMk (v := w.val) w.prop = C₀ := by simp only [C₀] unfold SimpleGraph.componentComplMk exact (SimpleGraph.ConnectedComponent.sound (hSreach w hw)).symm rw [← heq] exact G.componentComplMk_mem w.prop have hinj : Function.Injective (fun w : ↥S => (⟨w.val.val, hmem w.val w.prop⟩ : {x : V // x ∈ C₀})) := by intro a b hab simp only [Subtype.mk.injEq] at hab exact Subtype.ext (Subtype.ext hab) have hle : Fintype.card ↥S ≤ Fintype.card {x : V // x ∈ C₀} := Fintype.card_le_of_injective _ hinj rw [Fintype.card_coe] at hle have hC₀' : Fintype.card {x : V // x ∈ C₀} ≤ 3 := by rw [← Nat.card_eq_fintype_card] exact hC₀ omega/-- Refutation of Question 5.4 of arXiv:2611.05178: not every subcubic triangle-free non-bipartite graph admits an independent set whose complement has all connected components of order at most 3. -/theorem subcubic_odd_girth_five_partition_component_le_three_negation : ¬ (∀ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], G.maxDegree ≤ 3 → G.CliqueFree 3 → ¬G.IsBipartite → ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, open scoped Classical in Fintype.card C ≤ 3) := by intro H classical obtain ⟨L, hind, hcomp⟩ := H subcubic_odd_girth_five_partition_component_le_three_negation_wg subcubic_odd_girth_five_partition_component_le_three_negation_wg_maxDegree subcubic_odd_girth_five_partition_component_le_three_negation_wg_cliqueFree subcubic_odd_girth_five_partition_component_le_three_negation_wg_not_bipartite have hL : ∀ x ∈ L, ∀ y ∈ L, x ≠ y → ¬ subcubic_odd_girth_five_partition_component_le_three_negation_wg.Adj x y := by intro x hx y hy hxy hadj have hadj' : (subcubic_odd_girth_five_partition_component_le_three_negation_wg.induce (↑L)).Adj ⟨x, by simpa using hx⟩ ⟨y, by simpa using hy⟩ := by rwa [SimpleGraph.induce_adj] rw [hind] at hadj' exact (SimpleGraph.bot_adj _ _).mp hadj' obtain ⟨v, hv⟩ := subcubic_odd_girth_five_partition_component_le_three_negation_wg_key L hL have hcomp' : ∀ C : subcubic_odd_girth_five_partition_component_le_three_negation_wg.ComponentCompl (↑L), Nat.card C ≤ 3 := by intro C rw [Nat.card_eq_fintype_card] exact hcomp C refine subcubic_odd_girth_five_partition_component_le_three_negation_card_contra subcubic_odd_girth_five_partition_component_le_three_negation_wg (↑L : Set _) v (S := Finset.univ.filter (fun w => (SimpleGraph.induce (↑L)ᶜ subcubic_odd_girth_five_partition_component_le_three_negation_wg).Reachable v w)) ?_ ?_ hcomp' · exact hv · intro w hw exact (Finset.mem_filter.mp hw).2