AFTD Auto-Formalizing Theoretical Domains

not_not_subcubic_odd_girth_five_partition_component_le_three_negation

theoremverifiedoriginal

The statement not_subcubic_odd_girth_five_partition_component_le_three_negation is false: The statement is ¬ (¬ (∀ ...)), which asserts the negation of subcubic_odd_girth_five_partition_component_le_three_negation. However, subcubic_odd_girth_five_partition_component_le_three_negation has already been proved in the knowledge base (via the Wagner graph M8 counterexample to the universal statement). Because P is true, ¬ P is false. The negation of this target statement is directly proved by applying the assumption h : ¬ P to the proved theorem subcubic_odd_girth_five_partition_component_le_three_negation.

Statement

theorem not_not_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
refutes `not_subcubic_odd_girth_five_partition_component_le_three_negation`
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem establishes the triple negation ¬¬¬P of the graph partition conjecture P, whose negation ¬P was already established by the theorem subcubic_odd_girth_five_partition_component_le_three_negation. The proof proceeds by contradiction: assuming ¬¬P, we apply this assumption directly to the proved counterexample theorem ¬P to obtain False.

  1. To prove the negated statement ¬(¬¬P), it suffices to derive a contradiction from the assumption ¬¬P.

    We introduce the hypothesis h : ¬¬P, which assumes for contradiction that the universal partition statement cannot be disproved. The goal is reduced to showing False.

    line 6

      intro h
  2. A contradiction is reached, completing the proof.

    The hypothesis h asserts that any proof of ¬P yields False. Applying h directly to subcubic_odd_girth_five_partition_component_le_three_negation, which proves ¬P, immediately produces the required contradiction.

    line 7

    uses subcubic_odd_girth_five_partition_component_le_three_negation

      exact h subcubic_odd_girth_five_partition_component_le_three_negation
subcubic_odd_girth_five_partition_component_le_three_negation
The negation of the universal conjecture: it is not the case that every finite, triangle-free, non-bipartite graph with maximum degree at most 3 has an independent set whose complement induces connected components of 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

theorem not_not_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  exact h subcubic_odd_girth_five_partition_component_le_three_negation
See it in the graphDiscuss this resultChallenge it