triangle_free_card_le_four_isBipartite
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
- triangle_free_subcubic_card_le_four_partitionEvery finite simple graph on at most 4 vertices with maximum degree at most 3 that is triangle-free admits a partition into an independent…
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.
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).
uses
SimpleGraph.is3Clique_triple_iff.mprclassical -- 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⟩)
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.
uses
SimpleGraph.mem_neighborFinset,Finset.mem_sdiffby_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
|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.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.card_le_card,Finset.card_sdiffhave 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
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.
uses
Finset.card_eq_three,Finset.mem_insert,Finset.mem_singleton,Finset.card_le_cardhave 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
(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.
uses
SimpleGraph.IsBipartiteWith.isBipartite,Finset.coe_sdiff,Finset.coe_univ,Set.disjoint_sdiff_right,Or.inl,Or.inrrefine 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]))
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.
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
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).
uses
SimpleGraph.Coloring.mk,lt_or_gt_of_nerefine ⟨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
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.
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
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.
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.
- The proof relies on classical logic (line 5) and uses `omega` for linear arithmetic on set cardinalities and index inequalities.
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 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