AFTD Auto-Formalizing Theoretical Domains

triangle_free_card_le_four_isBipartite

theoremverified

Every finite simple graph on at most 4 vertices that is triangle-free is bipartite (2-colorable).

Statement

theorem triangle_free_card_le_four_isBipartite {V : Type*} [Fintype V]
    (G : SimpleGraph V) (htf : G.CliqueFree 3) (hcard : Fintype.card V ≤ 4) :
    G.IsBipartite
Source
step towards triangle_free_subcubic_card_le_four_partition
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
Used by 1

The proof, explained

The proof proceeds by case analysis on whether G has a vertex of degree at least 2. In Case 1, a vertex v with two distinct neighbours yields a bipartition into N(v) and its complement T = V \ N(v): triangle-freeness makes N(v) independent, while T contains at most 4 - 2 = 2 vertices including v (which has no edges in T), forcing T to also be independent. In Case 2, every vertex has degree at most 1, so G is a matching; using a linear ordering on vertices, assigning color 0 to the smaller endpoint of each edge and color 1 to the larger endpoint produces a valid 2-coloring.

  1. In a triangle-free graph, no three vertices are pairwise adjacent.

    Suppose three vertices a, b, c are pairwise adjacent. By SimpleGraph.is3Clique_triple_iff.mpr, {a, b, c} is a 3-clique (triangle). This directly contradicts the assumption htf that G is triangle-free (CliqueFree 3).

    lines 5–9

    uses SimpleGraph.is3Clique_triple_iff.mpr

      classical
      -- In a triangle-free graph, three pairwise adjacent vertices are impossible.
      have no3 : ∀ a b c : V, G.Adj a b → G.Adj a c → G.Adj b c → False := by
        intro a b c hab hac hbc
        exact htf {a, b, c} (SimpleGraph.is3Clique_triple_iff.mpr ⟨hab, hac, hbc⟩)
  2. Split into cases on whether some vertex has two distinct neighbours; in Case 1, fix such a vertex v with distinct neighbours u, w, and define N(v) and T = V \ N(v).

    We perform a case split on whether there exists a vertex v with two distinct neighbours u and w. In the positive case, we obtain such v, u, w, set Nv = N(v) to be the neighbor finset of v, and T = V \ N(v) to be its complement. By SimpleGraph.mem_neighborFinset, x ∈ Nv if and only if G.Adj v x. By Finset.mem_sdiff, x ∈ T if and only if ¬ G.Adj v x.

    lines 10–23

    uses SimpleGraph.mem_neighborFinset, Finset.mem_sdiff

      by_cases hex : ∃ v : V, ∃ u w : V, G.Adj v u ∧ G.Adj v w ∧ u ≠ w
      · -- Case 1: some vertex `v` has two distinct neighbours `u`, `w`.
        -- Partition the vertices into `Nv = N(v)` and its complement `T`.
        -- `Nv` is independent (triangle-freeness) and `T` is independent because it has at most
        -- `4 - 2 = 2` elements and contains `v`, which is adjacent to nothing in `T`.
        obtain ⟨v, u, w, hvu, hvw, huw⟩ := hex
        set Nv : Finset V := G.neighborFinset v with hNv
        set T : Finset V := Finset.univ \ Nv with hT
        have hNvmem : ∀ x : V, x ∈ Nv ↔ G.Adj v x := by
          intro x; rw [hNv, SimpleGraph.mem_neighborFinset]
        have hTmem : ∀ x : V, x ∈ T ↔ ¬ G.Adj v x := by
          intro x
          rw [hT, Finset.mem_sdiff, hNvmem]
          simp
  3. |N(v)| ≥ 2 and |T| ≤ 2.

    Since u and w are distinct neighbours of v, {u, w} ⊆ Nv (using Finset.mem_insert and Finset.mem_singleton), so |Nv| ≥ |{u, w}| = 2 by Finset.card_le_card. By Finset.card_sdiff, |T| = |V| - |Nv|. Since |V| ≤ 4 and |Nv| ≥ 2, linear arithmetic (omega) yields |T| ≤ 2.

    lines 24–38

    uses Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card, Finset.card_sdiff

        have hNvcard : 2 ≤ Nv.card := by
          have hsub : ({u, w} : Finset V) ⊆ Nv := by
            intro x hx
            rw [hNvmem]
            simp only [Finset.mem_insert, Finset.mem_singleton] at hx
            rcases hx with rfl | rfl
            · exact hvu
            · exact hvw
          have h2 : ({u, w} : Finset V).card = 2 := by simp [huw]
          calc 2 = ({u, w} : Finset V).card := h2.symm
            _ ≤ Nv.card := Finset.card_le_card hsub
        have hTcard : T.card ≤ 2 := by
          have h1 : T.card = Fintype.card V - Nv.card := by
            rw [hT, Finset.card_sdiff]; simp
          omega
  4. v ∈ T, and T is an independent set.

    Because simple graphs are irreflexive, v is not adjacent to itself, so v ∈ T. If there were adjacent vertices a, b ∈ T, then neither could be v (since vertices in T have no edge to v), and a ≠ b. Hence {v, a, b} consists of three pairwise distinct vertices by Finset.card_eq_three, and all three lie in T (using Finset.mem_insert and Finset.mem_singleton). By Finset.card_le_card, |T| ≥ 3, contradicting |T| ≤ 2.

    lines 39–59

    uses Finset.card_eq_three, Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card

        have hvT : v ∈ T := by rw [hTmem]; exact G.irrefl
        have hTindep : ∀ a ∈ T, ∀ b ∈ T, ¬ G.Adj a b := by
          intro a ha b hb hab
          have hav : a ≠ v := by
            rintro rfl
            exact absurd hab ((hTmem b).mp hb)
          have hbv : b ≠ v := by
            rintro rfl
            exact absurd hab.symm ((hTmem a).mp ha)
          have h3 : ({v, a, b} : Finset V).card = 3 := by
            rw [Finset.card_eq_three]
            exact ⟨v, a, b, hav.symm, hbv.symm, hab.ne, rfl⟩
          have hsub : ({v, a, b} : Finset V) ⊆ T := by
            intro x hx
            simp only [Finset.mem_insert, Finset.mem_singleton] at hx
            rcases hx with rfl | rfl | rfl
            · exact hvT
            · exact ha
            · exact hb
          have hc := Finset.card_le_card hsub
          omega
  5. (N(v), T) forms a bipartite partition of G, concluding Case 1.

    By SimpleGraph.IsBipartiteWith.isBipartite, it suffices to show Nv and T are disjoint and every edge crosses between them. Disjointness holds by Set.disjoint_sdiff_right via Finset.coe_sdiff and Finset.coe_univ. For any edge between a and b, if both were in Nv, then v, a, b would form a triangle, contradicting triangle-freeness (no3). If both were in T, it would contradict the independence of T (hTindep). Thus one endpoint is in Nv and the other in T, giving the disjuncts via Or.inl and Or.inr.

    lines 60–71

    uses SimpleGraph.IsBipartiteWith.isBipartite, Finset.coe_sdiff, Finset.coe_univ, Set.disjoint_sdiff_right, Or.inl, Or.inr

        refine SimpleGraph.IsBipartiteWith.isBipartite (s := (Nv : Set V)) (t := (T : Set V)) ⟨?_, ?_⟩
        · rw [hT]
          simp only [Finset.coe_sdiff, Finset.coe_univ]
          exact Set.disjoint_sdiff_right
        · intro a b hab
          by_cases ha : a ∈ Nv
          · by_cases hb : b ∈ Nv
            · exact absurd hab (no3 v a b ((hNvmem a).mp ha) ((hNvmem b).mp hb))
            · exact Or.inl ⟨by simpa using ha, by rw [hT]; simp [hb]⟩
          · by_cases hb : b ∈ Nv
            · exact Or.inr ⟨by rw [hT]; simp [ha], by simpa using hb⟩
            · exact absurd hab (hTindep a (by rw [hT]; simp [ha]) b (by rw [hT]; simp [hb]))
  6. In Case 2, every vertex has degree at most 1, and we define a candidate 2-coloring c.

    Negating the existence of a vertex with two distinct neighbours means every vertex has degree at most 1: any two neighbours of a vertex must be equal. We choose an enumeration e : V ≃ Fin |V| using Fintype.equivFin, which gives an injection into ℕ via Fin.ext. We define a 2-coloring c : V → Fin 2 by c(v) = 0 if v has a neighbour with a strictly larger index under e, and c(v) = 1 otherwise.

    lines 72–80

    uses Fintype.equivFin, Function.Injective, Fin.ext

      · -- Case 2: every vertex has at most one neighbour, so `G` is a matching.
        -- Colour each vertex `x` with `0` if `x` is the smaller endpoint (in a fixed linear order
        -- induced by `Fintype.equivFin V`) of its edge, and with `1` otherwise.
        push Not at hex
        let e := Fintype.equivFin V
        have hinj : Function.Injective (fun v : V => (e v : ℕ)) := by
          intro a b hab
          exact e.injective (Fin.ext hab)
        let c : V → Fin 2 := fun v => if ∃ w, G.Adj v w ∧ (e v : ℕ) < (e w : ℕ) then 0 else 1
  7. To show c is a proper coloring, consider an edge between a and b; their indices under e are unequal, so e(a) < e(b) or e(b) < e(a).

    By SimpleGraph.Coloring.mk, c is a proper coloring if adjacent vertices receive distinct colors. Since a and b are adjacent, a ≠ b, and injectivity of e implies e(a) ≠ e(b). By lt_or_gt_of_ne, either e(a) < e(b) or e(b) < e(a).

    lines 81–85

    uses SimpleGraph.Coloring.mk, lt_or_gt_of_ne

        refine ⟨SimpleGraph.Coloring.mk c ?_⟩
        intro a b hab
        have hab' : a ≠ b := hab.ne
        have hlt : (e a : ℕ) ≠ (e b : ℕ) := fun h => hab' (hinj h)
        rcases lt_or_gt_of_ne hlt with h | h
  8. If e(a) < e(b), then c(a) = 0 and c(b) = 1, so c(a) ≠ c(b).

    Since a is adjacent to b and e(a) < e(b), the condition defining c(a) holds with witness b, giving c(a) = 0 by if_pos. If c(b) were 0, b would have a neighbour x with e(b) < e(x). But b has at most one neighbour, so x must be a, which would force e(b) < e(a), a contradiction. Hence c(b) = 1 by if_neg. Finally, c(a) ≠ c(b) follows from zero_ne_one.

    lines 86–97

    uses if_pos, if_neg, zero_ne_one

        · have hca : c a = 0 := by
            simp only [c]
            exact if_pos ⟨b, hab, h⟩
          have hcb : c b = 1 := by
            simp only [c]
            apply if_neg
            rintro ⟨x, hbx, hltx⟩
            have hxa : x = a := hex b x a hbx hab.symm
            rw [hxa] at hltx
            omega
          rw [hca, hcb]
          exact zero_ne_one
  9. If e(b) < e(a), then symmetrically c(a) = 1 and c(b) = 0, so c(a) ≠ c(b), concluding the proof that G is bipartite.

    Symmetrically to the previous case, witness a gives c(b) = 0 by if_pos, while any potential witness for a would have to equal b, contradicting e(b) < e(a). Thus c(a) = 1 by if_neg. Therefore c(a) ≠ c(b) by one_ne_zero, which finishes the verification that c is a valid 2-coloring.

    lines 98–109

    uses if_neg, if_pos, one_ne_zero

        · have hca : c a = 1 := by
            simp only [c]
            apply if_neg
            rintro ⟨x, hax, hltx⟩
            have hxb : x = b := hex a x b hax hab
            rw [hxb] at hltx
            omega
          have hcb : c b = 0 := by
            simp only [c]
            exact if_pos ⟨a, hab.symm, h⟩
          rw [hca, hcb]
          exact one_ne_zero
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.card_eq_three
A finite set has cardinality 3 if and only if it consists of three pairwise distinct elements.
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.card_sdiff
The cardinality of the set difference t \ s is |t| - |s ∩ t|.
Finset.coe_sdiff
The set-coercion of a difference of finsets is the difference of their coercions.
Finset.coe_univ
The set-coercion of the universal finset is the universal set.
Finset.mem_insert
An element x is in insert b s if and only if x = b or x ∈ s.
Finset.mem_sdiff
An element is in the difference s \ t if and only if it is in s and not in t.
Finset.mem_singleton
An element b is in the singleton {a} if and only if b = a.
Fintype.equivFin
Every finite type α has an equivalence (bijection) with Fin |α|.
Function.Injective
A function is injective if distinct inputs map to distinct outputs.
if_neg
If a condition c is false, then (if c then t else e) = e.
if_pos
If a condition c is true, then (if c then t else e) = t.
lt_or_gt_of_ne
In a linear order, two unequal elements satisfy a < b or b < a.
one_ne_zero
One is not equal to zero.
Or.inl
The left injection into a disjunction: a implies a ∨ b.
Or.inr
The right injection into a disjunction: b implies a ∨ b.
Set.disjoint_sdiff_right
Any set s is disjoint from t \ s.
SimpleGraph.Coloring.mk
Constructs a proper graph coloring from a coloring function assigning different colors to adjacent vertices.
SimpleGraph.is3Clique_triple_iff.mpr
If three vertices are pairwise adjacent in a graph, then they form a 3-clique (triangle).
SimpleGraph.IsBipartiteWith.isBipartite
If a graph is bipartite with respect to a partition (s, t), then it is bipartite.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
zero_ne_one
Zero is not equal to one.

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 simple graph on at most 4 vertices that is triangle-free is bipartite. -/theorem triangle_free_card_le_four_isBipartite {V : Type*} [Fintype V]    (G : SimpleGraph V) (htf : G.CliqueFree 3) (hcard : Fintype.card V ≤ 4) :    G.IsBipartite := by  classical  -- In a triangle-free graph, three pairwise adjacent vertices are impossible.  have no3 : ∀ a b c : V, G.Adj a b → G.Adj a c → G.Adj b c → False := by    intro a b c hab hac hbc    exact htf {a, b, c} (SimpleGraph.is3Clique_triple_iff.mpr ⟨hab, hac, hbc⟩)  by_cases hex : ∃ v : V, ∃ u w : V, G.Adj v u ∧ G.Adj v w ∧ u ≠ w  · -- Case 1: some vertex `v` has two distinct neighbours `u`, `w`.    -- Partition the vertices into `Nv = N(v)` and its complement `T`.    -- `Nv` is independent (triangle-freeness) and `T` is independent because it has at most    -- `4 - 2 = 2` elements and contains `v`, which is adjacent to nothing in `T`.    obtain ⟨v, u, w, hvu, hvw, huw⟩ := hex    set Nv : Finset V := G.neighborFinset v with hNv    set T : Finset V := Finset.univ \ Nv with hT    have hNvmem : ∀ x : V, x ∈ Nv ↔ G.Adj v x := by      intro x; rw [hNv, SimpleGraph.mem_neighborFinset]    have hTmem : ∀ x : V, x ∈ T ↔ ¬ G.Adj v x := by      intro x      rw [hT, Finset.mem_sdiff, hNvmem]      simp    have hNvcard : 2 ≤ Nv.card := by      have hsub : ({u, w} : Finset V) ⊆ Nv := by        intro x hx        rw [hNvmem]        simp only [Finset.mem_insert, Finset.mem_singleton] at hx        rcases hx with rfl | rfl        · exact hvu        · exact hvw      have h2 : ({u, w} : Finset V).card = 2 := by simp [huw]      calc 2 = ({u, w} : Finset V).card := h2.symm        _ ≤ Nv.card := Finset.card_le_card hsub    have hTcard : T.card ≤ 2 := by      have h1 : T.card = Fintype.card V - Nv.card := by        rw [hT, Finset.card_sdiff]; simp      omega    have hvT : v ∈ T := by rw [hTmem]; exact G.irrefl    have hTindep : ∀ a ∈ T, ∀ b ∈ T, ¬ G.Adj a b := by      intro a ha b hb hab      have hav : a ≠ v := by        rintro rfl        exact absurd hab ((hTmem b).mp hb)      have hbv : b ≠ v := by        rintro rfl        exact absurd hab.symm ((hTmem a).mp ha)      have h3 : ({v, a, b} : Finset V).card = 3 := by        rw [Finset.card_eq_three]        exact ⟨v, a, b, hav.symm, hbv.symm, hab.ne, rfl⟩      have hsub : ({v, a, b} : Finset V) ⊆ T := by        intro x hx        simp only [Finset.mem_insert, Finset.mem_singleton] at hx        rcases hx with rfl | rfl | rfl        · exact hvT        · exact ha        · exact hb      have hc := Finset.card_le_card hsub      omega    refine SimpleGraph.IsBipartiteWith.isBipartite (s := (Nv : Set V)) (t := (T : Set V)) ⟨?_, ?_⟩    · rw [hT]      simp only [Finset.coe_sdiff, Finset.coe_univ]      exact Set.disjoint_sdiff_right    · intro a b hab      by_cases ha : a ∈ Nv      · by_cases hb : b ∈ Nv        · exact absurd hab (no3 v a b ((hNvmem a).mp ha) ((hNvmem b).mp hb))        · exact Or.inl ⟨by simpa using ha, by rw [hT]; simp [hb]⟩      · by_cases hb : b ∈ Nv        · exact Or.inr ⟨by rw [hT]; simp [ha], by simpa using hb⟩        · exact absurd hab (hTindep a (by rw [hT]; simp [ha]) b (by rw [hT]; simp [hb]))  · -- Case 2: every vertex has at most one neighbour, so `G` is a matching.    -- Colour each vertex `x` with `0` if `x` is the smaller endpoint (in a fixed linear order    -- induced by `Fintype.equivFin V`) of its edge, and with `1` otherwise.    push Not at hex    let e := Fintype.equivFin V    have hinj : Function.Injective (fun v : V => (e v : ℕ)) := by      intro a b hab      exact e.injective (Fin.ext hab)    let c : V → Fin 2 := fun v => if ∃ w, G.Adj v w ∧ (e v : ℕ) < (e w : ℕ) then 0 else 1    refine ⟨SimpleGraph.Coloring.mk c ?_⟩    intro a b hab    have hab' : a ≠ b := hab.ne    have hlt : (e a : ℕ) ≠ (e b : ℕ) := fun h => hab' (hinj h)    rcases lt_or_gt_of_ne hlt with h | h    · have hca : c a = 0 := by        simp only [c]        exact if_pos ⟨b, hab, h⟩      have hcb : c b = 1 := by        simp only [c]        apply if_neg        rintro ⟨x, hbx, hltx⟩        have hxa : x = a := hex b x a hbx hab.symm        rw [hxa] at hltx        omega      rw [hca, hcb]      exact zero_ne_one    · have hca : c a = 1 := by        simp only [c]        apply if_neg        rintro ⟨x, hax, hltx⟩        have hxb : x = b := hex a x b hax hab        rw [hxb] at hltx        omega      have hcb : c b = 0 := by        simp only [c]        exact if_pos ⟨a, hab.symm, h⟩      rw [hca, hcb]      exact one_ne_zero
See it in the graphDiscuss this resultChallenge it