AFTD Auto-Formalizing Theoretical Domains

subcubic_partition_component_le_three_of_card_le_three

theoremverified

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.

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

    lines 8–9

      use ∅
      constructor
  2. 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.

    lines 10–11

      · ext ⟨x, hx⟩
        simp at hx
  3. 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.

    lines 12–14

    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

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