AFTD Auto-Formalizing Theoretical Domains

triangle_free_subcubic_card_le_four_partition

theoremverified

Every finite simple graph on at most 4 vertices with maximum degree at most 3 that is triangle-free admits a partition into an independent set L and complement R = Lᶜ such that G[R] is bipartite and for every connected component C of G[R] and every vertex v in L, the induced subgraph on V(C) ∪ {v} is bipartite.

Statement

theorem triangle_free_subcubic_card_le_four_partition
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
    (hdeg : G.maxDegree ≤ 3) (htf : G.CliqueFree 3)
    (hcard : Fintype.card V ≤ 4) :
    ∃ L : Finset V,
      G.induce (L : Set V) = ⊥ ∧
      (G.induce (Lᶜ : Set V)).IsBipartite ∧
      ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent,
        ∀ v ∈ L, (G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite
Source
scout/2611-05178-weighted-max-cut-in-subcubic-graphs.md:1025
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Assume that: 1. the maximum degree of $G$ is at most 3 (G.maxDegree ≤ 3), 2. $G$ is triangle-free / contains no 3-cliques (G.CliqueFree 3), and 3. the number of vertices in $V$ is at most 4 (Fintype.card V ≤ 4). Then there exists a finite subset $L \subseteq V$ such that: 1. the subgraph of $G$ induced by $L$ has no edges (i.e., $L$ is an independent set, G.induce (L : Set V) = ⊥), 2. the subgraph of $G$ induced by the complement $L^c$ is bipartite ((G.induce (Lᶜ : Set V)).IsBipartite), and 3. for every connected component $C$ of the induced subgraph $G[L^c]$ and every vertex $v \in L$, the subgraph of $G$ induced by the vertices of $C$ along with $v$ is bipartite ((G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite).

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 requires finding an independent set L such that the complement subgraph G[Lᶜ] is bipartite and extending any component of G[Lᶜ] by any vertex in L remains bipartite. The proof simply chooses L = ∅, which is trivially an independent set and satisfies the component-extension condition vacuously. The remaining goal, that G[Lᶜ] = G[V] is bipartite, then follows from the fact that any triangle-free simple graph on at most 4 vertices is bipartite.

  1. Choosing L = ∅ reduces the theorem to verifying three conditions: the induced subgraph on ∅ is empty, the induced subgraph on ∅ᶜ is bipartite, and the component-extension condition holds.

    We instantiate the existential quantifier with the empty finset L = ∅. This produces three subgoals: showing that the induced subgraph on ∅ is the empty graph ⊥ (i.e. L is an independent set), showing that the induced subgraph on the complement ∅ᶜ is bipartite, and showing that every component of the complement graph remains bipartite when joined with any vertex in L.

    line 12

      refine ⟨∅, ?_, ?_, ?_⟩
  2. The induced subgraph on L = ∅ is the empty graph ⊥.

    Coercing the empty finset to a set yields the empty set ∅ (lines 13–14). By Set.isEmpty_coe_sort, the subtype of elements in ∅ is an empty type (line 15). Since simple graphs on an empty type form a subsingleton, Subsingleton.elim proves that the induced subgraph on ∅ is equal to the empty graph ⊥ (line 16).

    lines 13–16

    uses Set.isEmpty_coe_sort, Subsingleton.elim

      · have hset0 : ((∅ : Finset V) : Set V) = (∅ : Set V) := by simp
        rw [hset0]
        haveI : IsEmpty ↥(∅ : Set V) := by rw [Set.isEmpty_coe_sort]
        exact Subsingleton.elim _ _
  3. The induced subgraph on the complement Lᶜ = V is bipartite.

    Because G is a triangle-free graph on at most 4 vertices, a prior theorem (triangle_free_card_le_four_isBipartite) shows that G itself is bipartite (line 17). The complement of the empty set is the universal set Set.univ (lines 18–19). By definition, the induced subgraph on Set.univ is the pullback graph along the subtype inclusion embedding (lines 20–21). Using SimpleGraph.Colorable.of_hom along the canonical homomorphism SimpleGraph.Hom.comap, the bipartiteness (2-colorability) of G pulls back to the induced subgraph on Set.univ (lines 22–23).

    lines 17–23

    uses triangle_free_card_le_four_isBipartite, SimpleGraph.Colorable.of_hom, SimpleGraph.Hom.comap

      · have hb : G.IsBipartite := triangle_free_card_le_four_isBipartite G htf hcard
        have hset : ((∅ : Finset V)ᶜ : Set V) = Set.univ := by simp
        rw [hset]
        rw [show G.induce (Set.univ : Set V) =
          G.comap (Function.Embedding.subtype (· ∈ (Set.univ : Set V))) from rfl]
        exact SimpleGraph.Colorable.of_hom
          (SimpleGraph.Hom.comap (Function.Embedding.subtype (· ∈ (Set.univ : Set V))) G) hb
  4. For every connected component C of G[Lᶜ] and every vertex v ∈ L, the induced subgraph on V(C) ∪ {v} is bipartite.

    We introduce a connected component C, a vertex v, and the hypothesis hv that v ∈ ∅ (line 24). Simplifying this hypothesis reveals a contradiction, as the empty set has no members, which closes the goal vacuously (line 25).

    lines 24–25

      · intro C v hv
        simp at hv
Set.isEmpty_coe_sort
A set's coerced subtype is empty if and only if the set is empty.
Subsingleton.elim
Any two terms of a subsingleton type (a type with at most one term) are equal.
triangle_free_card_le_four_isBipartite
Every finite triangle-free simple graph on at most 4 vertices is bipartite.
SimpleGraph.Colorable.of_hom
A graph homomorphism from G to G' pulls an n-coloring of G' back to an n-coloring of G; in particular, if G' is bipartite (2-colorable), then so is G.
SimpleGraph.Hom.comap
For any vertex map f, the canonical map from the pullback graph comap f G to G is a graph homomorphism.

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 finite triangle-free subcubic simple graph on at most 4 vertices admits an independent-bipartite component partition. -/theorem triangle_free_subcubic_card_le_four_partition    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (hdeg : G.maxDegree ≤ 3) (htf : G.CliqueFree 3)    (hcard : Fintype.card V ≤ 4) :    ∃ L : Finset V,      G.induce (L : Set V) = ⊥ ∧      (G.induce (Lᶜ : Set V)).IsBipartite ∧      ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent,        ∀ v ∈ L, (G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite := by  refine ⟨∅, ?_, ?_, ?_⟩  · have hset0 : ((∅ : Finset V) : Set V) = (∅ : Set V) := by simp    rw [hset0]    haveI : IsEmpty ↥(∅ : Set V) := by rw [Set.isEmpty_coe_sort]    exact Subsingleton.elim _ _  · have hb : G.IsBipartite := triangle_free_card_le_four_isBipartite G htf hcard    have hset : ((∅ : Finset V)ᶜ : Set V) = Set.univ := by simp    rw [hset]    rw [show G.induce (Set.univ : Set V) =      G.comap (Function.Embedding.subtype (· ∈ (Set.univ : Set V))) from rfl]    exact SimpleGraph.Colorable.of_hom      (SimpleGraph.Hom.comap (Function.Embedding.subtype (· ∈ (Set.univ : Set V))) G) hb  · intro C v hv    simp at hv
See it in the graphDiscuss this resultChallenge it