subcubic_odd_girth_seven_partition_of_card_le_five
Every finite simple graph G on at most 5 vertices admits a partition into an independent set L and a subset R = Lᶜ such that every connected component of the induced subgraph G[R] has at most 5 vertices.
Statement
open SimpleGraph in open scoped Classical in theorem subcubic_odd_girth_seven_partition_of_card_le_five {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V ≤ 5) : ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, Fintype.card C ≤ 5
- Source
- folklore
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
Let $V$ be a finite type with decidable equality, let $G$ be a simple graph on $V$ with decidable adjacency, and suppose the cardinality of $V$ is at most 5. Then there exists a finite subset $L \subseteq V$ such that the induced subgraph $G[L]$ has no edges (i.e., $G.induce (L : Set V) = ⊥$), and for every connected component $C$ of the induced subgraph $G[V \setminus L]$, the number of vertices in $C$ is at most 5.
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 holds trivially by choosing the independent set to be the empty set L = ∅. The induced subgraph on the empty set is vacuously empty (has no edges), while the complement contains at most 5 vertices in total, so any connected component in it necessarily has at most 5 vertices.
We choose the empty set L = ∅, splitting the goal into showing that G[∅] has no edges and that every component in the complement has at most 5 vertices.
We provide the empty set ∅ as the witness for the existential quantifier L. Applying `constructor` splits the conjunction into two subgoals: proving that the induced subgraph G[∅] is the empty graph ⊥, and verifying that every connected component of G[∅ᶜ] has cardinality at most 5.
use ∅ constructor
The induced subgraph on the empty set has no edges: G[∅] = ⊥.
By extensionality, we show the adjacency relations coincide for any vertex ⟨x, hx⟩ in the induced subgraph. But hx asserts that x belongs to the empty set; rewriting with `Finset.coe_empty` and `Set.mem_empty_iff_false` reduces hx to False, completing the vacuous proof.
uses
Finset.coe_empty,Set.mem_empty_iff_false· ext ⟨x, hx⟩ simp only [Finset.coe_empty, Set.mem_empty_iff_false] at hx
Every connected component of G[∅ᶜ] has at most 5 vertices.
Let C be an arbitrary connected component of G[∅ᶜ]. Since C is defined as a subtype of vertices, its cardinality is at most the total number of vertices |V| by `Fintype.card_subtype_le`. Because |V| ≤ 5 by hypothesis, linear arithmetic (`omega`) concludes that |C| ≤ 5.
uses
Fintype.card_subtype_le· intro C have : Fintype.card C ≤ Fintype.card V := Fintype.card_subtype_le _ omega
Finset.coe_empty- The coercion of the empty finset to a set is the empty set ∅.
Set.mem_empty_iff_false- No element belongs to the empty set; x ∈ ∅ is logically equivalent to false.
Fintype.card_subtype_le- The cardinality of a subtype is bounded above by the cardinality of the ambient finite type.
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.
open SimpleGraph inopen scoped Classical in/-- Every finite simple graph with at most 5 vertices trivially admits a partition with component order at most 5. -/theorem subcubic_odd_girth_seven_partition_of_card_le_five {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V ≤ 5) : ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, Fintype.card C ≤ 5 := by use ∅ constructor · ext ⟨x, hx⟩ simp only [Finset.coe_empty, Set.mem_empty_iff_false] at hx · intro C have : Fintype.card C ≤ Fintype.card V := Fintype.card_subtype_le _ omega