subcubic_partition_component_le_three_of_card_le_three
Every finite simple graph on at most 3 vertices 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_partition_component_le_three_of_card_le_three {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V ≤ 3) : ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, open scoped Classical in Fintype.card C ≤ 3
- Source
- arXiv:2611.05178 Question 5.4 -- Weighted Max Cut in Subcubic Graphs
- 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 vertex set $V$ with decidable adjacency. Suppose that the number of vertices of $V$ is at most 3 ($|V| \le 3$). Then, there exists a finite subset $L \subseteq V$ such that: 1. The induced subgraph of $G$ on $L$ is edgeless ($G[\,L\,] = \bot$, i.e., $L$ is an independent set), and 2. For every connected component $C$ of the subgraph of $G$ induced on the complement $V \setminus L$, the number of vertices in $C$ (evaluated classically) is at most 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
We choose the independent set L to be the empty set ∅. Its induced subgraph is vacuously empty. Since the ambient vertex set V has at most 3 vertices, every connected component of the complement graph has size at most |V| ≤ 3 by monotonicity of subtype cardinality.
It suffices to show that the empty set is independent and that every component in its complement has at most 3 vertices.
We choose L = ∅ as the witness for the independent set and split the goal into two obligations: verifying that the induced subgraph on ∅ is empty (has no edges), and bounding the cardinality of every connected component of the complement graph.
use ∅ constructor
The induced subgraph on the empty set is the empty graph ⊥. automation
By extensionality on graphs, any potential edge must join vertices belonging to the vertex set ∅. Since the empty set has no elements, simplifying the membership hypothesis hx : x ∈ ∅ yields a contradiction, closing the branch.
· ext ⟨x, hx⟩ simp at hx
Every connected component of the complement graph has cardinality at most 3.
Let C be a connected component of the complement graph. By Fintype.card_subtype_le, the number of vertices in C is at most the total number of vertices |V|. Since |V| ≤ 3 by assumption hcard, transitivity of ≤ implies that |C| ≤ 3.
uses
Fintype.card_subtype_le· intro C classical exact (Fintype.card_subtype_le (· ∈ C)).trans hcard
Fintype.card_subtype_le- The cardinality of any subtype { x // p x } is at most the cardinality of the ambient 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.
/-- Every graph on at most 3 vertices admits an independent set whose complement has all connected components of order at most 3. -/theorem subcubic_partition_component_le_three_of_card_le_three {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V ≤ 3) : ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, open scoped Classical in Fintype.card C ≤ 3 := by use ∅ constructor · ext ⟨x, hx⟩ simp at hx · intro C classical exact (Fintype.card_subtype_le (· ∈ C)).trans hcard