AFTD Auto-Formalizing Theoretical Domains

subcubic_odd_girth_five_partition_component_le_three_negation

theoremverifiedoriginal

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

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.

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

    lines 10–14

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

    lines 16–19

    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
    
  3. 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`.

    lines 21–25

    uses SimpleGraph.CliqueFree

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

    lines 27–37

    uses SimpleGraph.IsBipartite, SimpleGraph.Colorable

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

    lines 41–50

    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
    
  6. 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₀.

    lines 55–71

    uses SimpleGraph.ConnectedComponent.sound

    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
  7. 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`).

    lines 72–84

    uses Subtype.ext, Fintype.card_le_of_injective, Fintype.card_coe, Nat.card_eq_fintype_card

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

    lines 92–97

    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_bipartite

      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
  9. 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`.

    lines 98–105

    uses SimpleGraph.induce_adj, SimpleGraph.bot_adj

      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'
  10. 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`.

    lines 106–112

    uses subcubic_odd_girth_five_partition_component_le_three_negation_wg_key, Nat.card_eq_fintype_card

      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
  11. 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`.

    lines 113–120

    uses subcubic_odd_girth_five_partition_component_le_three_negation_card_contra

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

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

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