AFTD Auto-Formalizing Theoretical Domains

subcubic_odd_girth_seven_partition_of_card_le_five

theoremverified

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.

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

    lines 9–10

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

    lines 11–12

    uses Finset.coe_empty, Set.mem_empty_iff_false

      · ext ⟨x, hx⟩
        simp only [Finset.coe_empty, Set.mem_empty_iff_false] at hx
  3. 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.

    lines 13–15

    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

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