not_not_subcubic_odd_girth_five_partition_component_le_three_negation
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
- subcubic_odd_girth_five_partition_component_le_three_negationIt 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…
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.
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.
intro hA 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.
uses
subcubic_odd_girth_five_partition_component_le_three_negationexact 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
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.
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