/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import Mathlib.Combinatorics.SimpleGraph.Coloring.Vertex
public import Mathlib.Data.Finite.Sum
public import Mathlib.Data.Fintype.Option
public import Mathlib.Tactic.SplitIfsThe Mycielski construction
The Mycielski construction preserves triangle-freeness and increases a finite chromatic number by one. Iteration gives finite graphs of clique number two with every chromatic number at least two.
References
J. Mycielski, Sur le coloriage des graphs, Colloquium Mathematicum 3 (1955), 161–162. doi:10.4064/cm-3-2-161-162
@[expose] public sectionnamespace SimpleGraphvariable {V : Type*}
The adjacency relation of the Mycielski construction. The apex is none;
original vertices use Sum.inl, and shadow vertices use Sum.inr.
def mycielskiAdj (G : SimpleGraph V) : Option (V ⊕ V) → Option (V ⊕ V) → Prop
| none, some (.inr _) => True
| some (.inr _), none => True
| some (.inl v), some (.inl w) => G.Adj v w
| some (.inl v), some (.inr w) => G.Adj v w
| some (.inr v), some (.inl w) => G.Adj v w
| _, _ => FalseThe Mycielski construction adds a shadow copy of the vertices and an apex.
def mycielski (G : SimpleGraph V) : SimpleGraph (Option (V ⊕ V)) where
Adj := mycielskiAdj G
symm := ⟨V:Type u_1G:SimpleGraph V⊢ ∀ (a b : Option (V ⊕ V)), G.mycielskiAdj a b → G.mycielskiAdj b a
V:Type u_1G:SimpleGraph V⊢ G.mycielskiAdj none none → G.mycielskiAdj none noneV:Type u_1G:SimpleGraph Vval✝:V⊢ G.mycielskiAdj none (some (Sum.inl val✝)) → G.mycielskiAdj (some (Sum.inl val✝)) noneV:Type u_1G:SimpleGraph Vval✝:V⊢ G.mycielskiAdj none (some (Sum.inr val✝)) → G.mycielskiAdj (some (Sum.inr val✝)) noneV:Type u_1G:SimpleGraph Vval✝:V⊢ G.mycielskiAdj (some (Sum.inl val✝)) none → G.mycielskiAdj none (some (Sum.inl val✝))V:Type u_1G:SimpleGraph Vval✝¹:Vval✝:V⊢ G.mycielskiAdj (some (Sum.inl val✝¹)) (some (Sum.inl val✝)) →
G.mycielskiAdj (some (Sum.inl val✝)) (some (Sum.inl val✝¹))V:Type u_1G:SimpleGraph Vval✝¹:Vval✝:V⊢ G.mycielskiAdj (some (Sum.inl val✝¹)) (some (Sum.inr val✝)) →
G.mycielskiAdj (some (Sum.inr val✝)) (some (Sum.inl val✝¹))V:Type u_1G:SimpleGraph Vval✝:V⊢ G.mycielskiAdj (some (Sum.inr val✝)) none → G.mycielskiAdj none (some (Sum.inr val✝))V:Type u_1G:SimpleGraph Vval✝¹:Vval✝:V⊢ G.mycielskiAdj (some (Sum.inr val✝¹)) (some (Sum.inl val✝)) →
G.mycielskiAdj (some (Sum.inl val✝)) (some (Sum.inr val✝¹))V:Type u_1G:SimpleGraph Vval✝¹:Vval✝:V⊢ G.mycielskiAdj (some (Sum.inr val✝¹)) (some (Sum.inr val✝)) →
G.mycielskiAdj (some (Sum.inr val✝)) (some (Sum.inr val✝¹)) V:Type u_1G:SimpleGraph V⊢ G.mycielskiAdj none none → G.mycielskiAdj none noneV:Type u_1G:SimpleGraph Vval✝:V⊢ G.mycielskiAdj none (some (Sum.inl val✝)) → G.mycielskiAdj (some (Sum.inl val✝)) noneV:Type u_1G:SimpleGraph Vval✝:V⊢ G.mycielskiAdj none (some (Sum.inr val✝)) → G.mycielskiAdj (some (Sum.inr val✝)) noneV:Type u_1G:SimpleGraph Vval✝:V⊢ G.mycielskiAdj (some (Sum.inl val✝)) none → G.mycielskiAdj none (some (Sum.inl val✝))V:Type u_1G:SimpleGraph Vval✝¹:Vval✝:V⊢ G.mycielskiAdj (some (Sum.inl val✝¹)) (some (Sum.inl val✝)) →
G.mycielskiAdj (some (Sum.inl val✝)) (some (Sum.inl val✝¹))V:Type u_1G:SimpleGraph Vval✝¹:Vval✝:V⊢ G.mycielskiAdj (some (Sum.inl val✝¹)) (some (Sum.inr val✝)) →
G.mycielskiAdj (some (Sum.inr val✝)) (some (Sum.inl val✝¹))V:Type u_1G:SimpleGraph Vval✝:V⊢ G.mycielskiAdj (some (Sum.inr val✝)) none → G.mycielskiAdj none (some (Sum.inr val✝))V:Type u_1G:SimpleGraph Vval✝¹:Vval✝:V⊢ G.mycielskiAdj (some (Sum.inr val✝¹)) (some (Sum.inl val✝)) →
G.mycielskiAdj (some (Sum.inl val✝)) (some (Sum.inr val✝¹))V:Type u_1G:SimpleGraph Vval✝¹:Vval✝:V⊢ G.mycielskiAdj (some (Sum.inr val✝¹)) (some (Sum.inr val✝)) →
G.mycielskiAdj (some (Sum.inr val✝)) (some (Sum.inr val✝¹)) All goals completed! 🐙⟩
loopless := ⟨V:Type u_1G:SimpleGraph V⊢ ∀ (a : Option (V ⊕ V)), ¬G.mycielskiAdj a a
V:Type u_1G:SimpleGraph V⊢ ¬G.mycielskiAdj none noneV:Type u_1G:SimpleGraph Vval✝:V⊢ ¬G.mycielskiAdj (some (Sum.inl val✝)) (some (Sum.inl val✝))V:Type u_1G:SimpleGraph Vval✝:V⊢ ¬G.mycielskiAdj (some (Sum.inr val✝)) (some (Sum.inr val✝)) V:Type u_1G:SimpleGraph V⊢ ¬G.mycielskiAdj none noneV:Type u_1G:SimpleGraph Vval✝:V⊢ ¬G.mycielskiAdj (some (Sum.inl val✝)) (some (Sum.inl val✝))V:Type u_1G:SimpleGraph Vval✝:V⊢ ¬G.mycielskiAdj (some (Sum.inr val✝)) (some (Sum.inr val✝)) All goals completed! 🐙⟩@[simp] theorem mycielski_adj (G : SimpleGraph V) (v w : Option (V ⊕ V)) :
G.mycielski.Adj v w ↔ mycielskiAdj G v w := Iff.rflvariable {G : SimpleGraph V} {α : Type*} {k : ℕ}Extend a coloring by giving the apex a new color and each shadow its original vertex's color.
def Coloring.mycielski (C : G.Coloring α) : G.mycielski.Coloring (Option α) :=
Coloring.mk
(fun
| none => none
| some (.inl v) => some (C v)
| some (.inr v) => some (C v))
(V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring α⊢ ∀ {v w : Option (V ⊕ V)},
G.mycielski.Adj v w →
(match v with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match w with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αh:G.mycielski.Adj none none⊢ (match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αval✝:Vh:G.mycielski.Adj none (some (Sum.inl val✝))⊢ (match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αw:Vh:G.mycielski.Adj none (some (Sum.inr w))⊢ (match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inr w) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αval✝:Vh:G.mycielski.Adj (some (Sum.inl val✝)) none⊢ (match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αval✝¹:Vval✝:Vh:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))⊢ (match some (Sum.inl val✝¹) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αval✝:Vw:Vh:G.mycielski.Adj (some (Sum.inl val✝)) (some (Sum.inr w))⊢ (match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inr w) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αv:Vh:G.mycielski.Adj (some (Sum.inr v)) none⊢ (match some (Sum.inr v) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αv:Vval✝:Vh:G.mycielski.Adj (some (Sum.inr v)) (some (Sum.inl val✝))⊢ (match some (Sum.inr v) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αv:Vw:Vh:G.mycielski.Adj (some (Sum.inr v)) (some (Sum.inr w))⊢ (match some (Sum.inr v) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inr w) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v) V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αh:G.mycielski.Adj none none⊢ (match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αval✝:Vh:G.mycielski.Adj none (some (Sum.inl val✝))⊢ (match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αw:Vh:G.mycielski.Adj none (some (Sum.inr w))⊢ (match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inr w) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αval✝:Vh:G.mycielski.Adj (some (Sum.inl val✝)) none⊢ (match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αval✝¹:Vval✝:Vh:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))⊢ (match some (Sum.inl val✝¹) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αval✝:Vw:Vh:G.mycielski.Adj (some (Sum.inl val✝)) (some (Sum.inr w))⊢ (match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inr w) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αv:Vh:G.mycielski.Adj (some (Sum.inr v)) none⊢ (match some (Sum.inr v) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match none with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αv:Vval✝:Vh:G.mycielski.Adj (some (Sum.inr v)) (some (Sum.inl val✝))⊢ (match some (Sum.inr v) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inl val✝) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.Coloring αv:Vw:Vh:G.mycielski.Adj (some (Sum.inr v)) (some (Sum.inr w))⊢ (match some (Sum.inr v) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)) ≠
match some (Sum.inr w) with
| none => none
| some (Sum.inl v) => some (C v)
| some (Sum.inr v) => some (C v)
All goals completed! 🐙)
A k-coloring extends to a (k + 1)-coloring of the Mycielski graph.
theorem Colorable.mycielski (h : G.Colorable k) : G.mycielski.Colorable (k + 1) := V:Type u_1G:SimpleGraph Vk:ℕh:G.Colorable k⊢ G.mycielski.Colorable (k + 1)
All goals completed! 🐙Recolor every original vertex with the apex color using its shadow's color. This produces a coloring of the original graph that omits the apex color.
noncomputable def Coloring.ofMycielski (C : G.mycielski.Coloring α) : G.Coloring α := V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring α⊢ G.Coloring α
classical
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring α⊢ ∀ {v w : V},
G.Adj v w →
(if C (some (Sum.inl v)) = C none then C (some (Sum.inr v)) else C (some (Sum.inl v))) ≠
if C (some (Sum.inl w)) = C none then C (some (Sum.inr w)) else C (some (Sum.inl w))
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v w⊢ (if C (some (Sum.inl v)) = C none then C (some (Sum.inr v)) else C (some (Sum.inl v))) ≠
if C (some (Sum.inl w)) = C none then C (some (Sum.inr w)) else C (some (Sum.inl w))
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))⊢ (if C (some (Sum.inl v)) = C none then C (some (Sum.inr v)) else C (some (Sum.inl v))) ≠
if C (some (Sum.inl w)) = C none then C (some (Sum.inr w)) else C (some (Sum.inl w))
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))⊢ (if C (some (Sum.inl v)) = C none then C (some (Sum.inr v)) else C (some (Sum.inl v))) ≠
if C (some (Sum.inl w)) = C none then C (some (Sum.inr w)) else C (some (Sum.inl w))
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))⊢ (if C (some (Sum.inl v)) = C none then C (some (Sum.inr v)) else C (some (Sum.inl v))) ≠
if C (some (Sum.inl w)) = C none then C (some (Sum.inr w)) else C (some (Sum.inl w))
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))hv:C (some (Sum.inl v)) = C nonehw:C (some (Sum.inl w)) = C none⊢ C (some (Sum.inr v)) ≠ C (some (Sum.inr w))V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))hv:C (some (Sum.inl v)) = C nonehw:¬C (some (Sum.inl w)) = C none⊢ C (some (Sum.inr v)) ≠ C (some (Sum.inl w))V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))hv:¬C (some (Sum.inl v)) = C noneh✝:C (some (Sum.inl w)) = C none⊢ C (some (Sum.inl v)) ≠ C (some (Sum.inr w))V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))hv:¬C (some (Sum.inl v)) = C noneh✝:¬C (some (Sum.inl w)) = C none⊢ C (some (Sum.inl v)) ≠ C (some (Sum.inl w))
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))hv:C (some (Sum.inl v)) = C nonehw:C (some (Sum.inl w)) = C none⊢ C (some (Sum.inr v)) ≠ C (some (Sum.inr w)) All goals completed! 🐙
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))hv:C (some (Sum.inl v)) = C nonehw:¬C (some (Sum.inl w)) = C none⊢ C (some (Sum.inr v)) ≠ C (some (Sum.inl w)) All goals completed! 🐙
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))hv:¬C (some (Sum.inl v)) = C noneh✝:C (some (Sum.inl w)) = C none⊢ C (some (Sum.inl v)) ≠ C (some (Sum.inr w)) All goals completed! 🐙
V:Type u_1G:SimpleGraph Vα:Type u_2k:ℕC:G.mycielski.Coloring αv:Vw:Vh:G.Adj v whoo:C (some (Sum.inl v)) ≠ C (some (Sum.inl w))hos:C (some (Sum.inl v)) ≠ C (some (Sum.inr w))hso:C (some (Sum.inr v)) ≠ C (some (Sum.inl w))hv:¬C (some (Sum.inl v)) = C noneh✝:¬C (some (Sum.inl w)) = C none⊢ C (some (Sum.inl v)) ≠ C (some (Sum.inl w)) All goals completed! 🐙The recolored original graph omits the apex color.
theorem Coloring.ofMycielski_ne_apex (C : G.mycielski.Coloring α) (v : V) :
C.ofMycielski v ≠ C none := V:Type u_1G:SimpleGraph Vα:Type u_2C:G.mycielski.Coloring αv:V⊢ C.ofMycielski v ≠ C none
classical
V:Type u_1G:SimpleGraph Vα:Type u_2C:G.mycielski.Coloring αv:V⊢ (if C (some (Sum.inl v)) = C none then C (some (Sum.inr v)) else C (some (Sum.inl v))) ≠ C none
V:Type u_1G:SimpleGraph Vα:Type u_2C:G.mycielski.Coloring αv:Vh:C (some (Sum.inl v)) = C none⊢ C (some (Sum.inr v)) ≠ C noneV:Type u_1G:SimpleGraph Vα:Type u_2C:G.mycielski.Coloring αv:Vh:¬C (some (Sum.inl v)) = C none⊢ C (some (Sum.inl v)) ≠ C none
V:Type u_1G:SimpleGraph Vα:Type u_2C:G.mycielski.Coloring αv:Vh:C (some (Sum.inl v)) = C none⊢ C (some (Sum.inr v)) ≠ C none All goals completed! 🐙
V:Type u_1G:SimpleGraph Vα:Type u_2C:G.mycielski.Coloring αv:Vh:¬C (some (Sum.inl v)) = C none⊢ C (some (Sum.inl v)) ≠ C none All goals completed! 🐙
A Mycielski graph is not k-colorable if the original graph has chromatic number at least k.
theorem not_colorable_mycielski (h : (k : ℕ∞) ≤ G.chromaticNumber) :
¬G.mycielski.Colorable k := V:Type u_1G:SimpleGraph Vk:ℕh:↑k ≤ G.chromaticNumber⊢ ¬G.mycielski.Colorable k
V:Type u_1G:SimpleGraph Vk:ℕh:↑k ≤ G.chromaticNumberC:G.mycielski.Coloring (Fin k)⊢ False
V:Type u_1G:SimpleGraph Vk:ℕh:↑k ≤ G.chromaticNumberC:G.mycielski.Coloring (Fin k)v:Vhv:C.ofMycielski v = C none⊢ False
All goals completed! 🐙The Mycielski construction increases a finite chromatic number by one.
theorem chromaticNumber_mycielski (h : G.chromaticNumber = (k : ℕ∞)) :
G.mycielski.chromaticNumber = ((k + 1 : ℕ) : ℕ∞) := V:Type u_1G:SimpleGraph Vk:ℕh:G.chromaticNumber = ↑k⊢ G.mycielski.chromaticNumber = ↑(k + 1)
All goals completed! 🐙The Mycielski construction preserves triangle-freeness.
theorem CliqueFree.mycielski {G : SimpleGraph V} (hG : G.CliqueFree 3) :
G.mycielski.CliqueFree 3 := V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3⊢ G.mycielski.CliqueFree 3
classical
V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → False⊢ G.mycielski.CliqueFree 3
V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 s⊢ False
V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sa:Option (V ⊕ V)b:Option (V ⊕ V)c:Option (V ⊕ V)hab:G.mycielski.Adj a bhac:G.mycielski.Adj a chbc:G.mycielski.Adj b c⊢ False
V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sb:Option (V ⊕ V)c:Option (V ⊕ V)hbc:G.mycielski.Adj b chab:G.mycielski.Adj none bhac:G.mycielski.Adj none c⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sb:Option (V ⊕ V)c:Option (V ⊕ V)hbc:G.mycielski.Adj b cval✝:Vhab:G.mycielski.Adj (some (Sum.inl val✝)) bhac:G.mycielski.Adj (some (Sum.inl val✝)) c⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sb:Option (V ⊕ V)c:Option (V ⊕ V)hbc:G.mycielski.Adj b cval✝:Vhab:G.mycielski.Adj (some (Sum.inr val✝)) bhac:G.mycielski.Adj (some (Sum.inr val✝)) c⊢ False V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sb:Option (V ⊕ V)c:Option (V ⊕ V)hbc:G.mycielski.Adj b chab:G.mycielski.Adj none bhac:G.mycielski.Adj none c⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sb:Option (V ⊕ V)c:Option (V ⊕ V)hbc:G.mycielski.Adj b cval✝:Vhab:G.mycielski.Adj (some (Sum.inl val✝)) bhac:G.mycielski.Adj (some (Sum.inl val✝)) c⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sb:Option (V ⊕ V)c:Option (V ⊕ V)hbc:G.mycielski.Adj b cval✝:Vhab:G.mycielski.Adj (some (Sum.inr val✝)) bhac:G.mycielski.Adj (some (Sum.inr val✝)) c⊢ False V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝)) chbc:G.mycielski.Adj none chab:G.mycielski.Adj (some (Sum.inr val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝¹:Vhac:G.mycielski.Adj (some (Sum.inr val✝)) cval✝:Vhbc:G.mycielski.Adj (some (Sum.inl val✝)) chab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝¹:Vhac:G.mycielski.Adj (some (Sum.inr val✝)) cval✝:Vhbc:G.mycielski.Adj (some (Sum.inr val✝)) chab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))⊢ False V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)hac:G.mycielski.Adj none chbc:G.mycielski.Adj none chab:G.mycielski.Adj none none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)hac:G.mycielski.Adj none cval✝:Vhbc:G.mycielski.Adj (some (Sum.inl val✝)) chab:G.mycielski.Adj none (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)hac:G.mycielski.Adj none cval✝:Vhbc:G.mycielski.Adj (some (Sum.inr val✝)) chab:G.mycielski.Adj none (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝:Vhac:G.mycielski.Adj (some (Sum.inl val✝)) chbc:G.mycielski.Adj none chab:G.mycielski.Adj (some (Sum.inl val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝¹:Vhac:G.mycielski.Adj (some (Sum.inl val✝)) cval✝:Vhbc:G.mycielski.Adj (some (Sum.inl val✝)) chab:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝¹:Vhac:G.mycielski.Adj (some (Sum.inl val✝)) cval✝:Vhbc:G.mycielski.Adj (some (Sum.inr val✝)) chab:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝)) chbc:G.mycielski.Adj none chab:G.mycielski.Adj (some (Sum.inr val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝¹:Vhac:G.mycielski.Adj (some (Sum.inr val✝)) cval✝:Vhbc:G.mycielski.Adj (some (Sum.inl val✝)) chab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sc:Option (V ⊕ V)val✝¹:Vhac:G.mycielski.Adj (some (Sum.inr val✝)) cval✝:Vhbc:G.mycielski.Adj (some (Sum.inr val✝)) chab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))⊢ False
V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vval✝:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))hac:G.mycielski.Adj (some (Sum.inr val✝)) nonehbc:G.mycielski.Adj (some (Sum.inr val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝²)) (some (Sum.inl val✝))hbc:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝²)) (some (Sum.inr val✝))hbc:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))⊢ False V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 shab:G.mycielski.Adj none nonehac:G.mycielski.Adj none nonehbc:G.mycielski.Adj none none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 shab:G.mycielski.Adj none noneval✝:Vhac:G.mycielski.Adj none (some (Sum.inl val✝))hbc:G.mycielski.Adj none (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 shab:G.mycielski.Adj none noneval✝:Vhac:G.mycielski.Adj none (some (Sum.inr val✝))hbc:G.mycielski.Adj none (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝:Vhab:G.mycielski.Adj none (some (Sum.inl val✝))hac:G.mycielski.Adj none nonehbc:G.mycielski.Adj (some (Sum.inl val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vhab:G.mycielski.Adj none (some (Sum.inl val✝))val✝:Vhac:G.mycielski.Adj none (some (Sum.inl val✝))hbc:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vhab:G.mycielski.Adj none (some (Sum.inl val✝))val✝:Vhac:G.mycielski.Adj none (some (Sum.inr val✝))hbc:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝:Vhab:G.mycielski.Adj none (some (Sum.inr val✝))hac:G.mycielski.Adj none nonehbc:G.mycielski.Adj (some (Sum.inr val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vhab:G.mycielski.Adj none (some (Sum.inr val✝))val✝:Vhac:G.mycielski.Adj none (some (Sum.inl val✝))hbc:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vhab:G.mycielski.Adj none (some (Sum.inr val✝))val✝:Vhac:G.mycielski.Adj none (some (Sum.inr val✝))hbc:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝:Vhab:G.mycielski.Adj (some (Sum.inl val✝)) nonehac:G.mycielski.Adj (some (Sum.inl val✝)) nonehbc:G.mycielski.Adj none none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vhab:G.mycielski.Adj (some (Sum.inl val✝)) noneval✝:Vhac:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))hbc:G.mycielski.Adj none (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vhab:G.mycielski.Adj (some (Sum.inl val✝)) noneval✝:Vhac:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inr val✝))hbc:G.mycielski.Adj none (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vval✝:Vhab:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))hac:G.mycielski.Adj (some (Sum.inl val✝)) nonehbc:G.mycielski.Adj (some (Sum.inl val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inl val✝²)) (some (Sum.inl val✝))hbc:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inl val✝²)) (some (Sum.inr val✝))hbc:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vval✝:Vhab:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inr val✝))hac:G.mycielski.Adj (some (Sum.inl val✝)) nonehbc:G.mycielski.Adj (some (Sum.inr val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inr val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inl val✝²)) (some (Sum.inl val✝))hbc:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inr val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inl val✝²)) (some (Sum.inr val✝))hbc:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝:Vhab:G.mycielski.Adj (some (Sum.inr val✝)) nonehac:G.mycielski.Adj (some (Sum.inr val✝)) nonehbc:G.mycielski.Adj none none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vhab:G.mycielski.Adj (some (Sum.inr val✝)) noneval✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))hbc:G.mycielski.Adj none (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vhab:G.mycielski.Adj (some (Sum.inr val✝)) noneval✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))hbc:G.mycielski.Adj none (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vval✝:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))hac:G.mycielski.Adj (some (Sum.inr val✝)) nonehbc:G.mycielski.Adj (some (Sum.inl val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝²)) (some (Sum.inl val✝))hbc:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝²)) (some (Sum.inr val✝))hbc:G.mycielski.Adj (some (Sum.inl val✝¹)) (some (Sum.inr val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝¹:Vval✝:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))hac:G.mycielski.Adj (some (Sum.inr val✝)) nonehbc:G.mycielski.Adj (some (Sum.inr val✝)) none⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝²)) (some (Sum.inl val✝))hbc:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inl val✝))⊢ FalseV:Type u_1G:SimpleGraph VhG:G.CliqueFree 3htri:∀ (a b c : V), G.Adj a b → G.Adj a c → G.Adj b c → Falses:Finset (Option (V ⊕ V))hs:G.mycielski.IsNClique 3 sval✝²:Vval✝¹:Vhab:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))val✝:Vhac:G.mycielski.Adj (some (Sum.inr val✝²)) (some (Sum.inr val✝))hbc:G.mycielski.Adj (some (Sum.inr val✝¹)) (some (Sum.inr val✝))⊢ False All goals completed! 🐙
all_goals All goals completed! 🐙A triangle-free graph has clique number at most two.
theorem CliqueFree.cliqueNum_le_two {G : SimpleGraph V} (hG : G.CliqueFree 3) :
G.cliqueNum ≤ 2 := V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3⊢ G.cliqueNum ≤ 2
V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3h:¬G.cliqueNum ≤ 2⊢ False
V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3h:¬G.cliqueNum ≤ 2s:Finset Vhs:G.IsNClique G.cliqueNum s⊢ False
exact (CliqueFree.mono (V:Type u_1G:SimpleGraph VhG:G.CliqueFree 3h:¬G.cliqueNum ≤ 2s:Finset Vhs:G.IsNClique G.cliqueNum s⊢ 3 ≤ G.cliqueNum All goals completed! 🐙 : 3 ≤ G.cliqueNum) hG) s hsThe Mycielski graph of a nonempty triangle-free finite graph has clique number two.
V:Type u_1inst✝¹:Finite Vinst✝:Nonempty VG:SimpleGraph VhG:G.CliqueFree 3v:Vhpair:G.mycielski.IsClique ↑{none, some (Sum.inr v)}⊢ 2 ≤ G.mycielski.cliqueNum
simpa using hpair.card_le_cliqueNum All goals completed! 🐙variable {W : Type*}Relabelling vertices preserves the clique number.
theorem cliqueNum_map_equiv (G : SimpleGraph V) (e : V ≃ W) :
(G.map e).cliqueNum = G.cliqueNum := by V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ W⊢ (SimpleGraph.map (⇑e) G).cliqueNum = G.cliqueNum
unfold cliqueNum V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ W⊢ sSup {n | ∃ s, (SimpleGraph.map (⇑e) G).IsNClique n s} = sSup {n | ∃ s, G.IsNClique n s}
congr 1 V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ W⊢ {n | ∃ s, (SimpleGraph.map (⇑e) G).IsNClique n s} = {n | ∃ s, G.IsNClique n s}
ext n V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ Wn:ℕ⊢ n ∈ {n | ∃ s, (SimpleGraph.map (⇑e) G).IsNClique n s} ↔ n ∈ {n | ∃ s, G.IsNClique n s}
change ((G.map e).cliqueSet n).Nonempty ↔ (G.cliqueSet n).Nonempty V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ Wn:ℕ⊢ ((SimpleGraph.map (⇑e) G).cliqueSet n).Nonempty ↔ (G.cliqueSet n).Nonempty
rw [cliqueSet_map_of_equiv V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ Wn:ℕ⊢ (Finset.map e.toEmbedding '' G.cliqueSet n).Nonempty ↔ (G.cliqueSet n).Nonempty V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ Wn:ℕ⊢ (Finset.map e.toEmbedding '' G.cliqueSet n).Nonempty ↔ (G.cliqueSet n).Nonempty] V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ Wn:ℕ⊢ (Finset.map e.toEmbedding '' G.cliqueSet n).Nonempty ↔ (G.cliqueSet n).Nonempty
exact Set.image_nonempty All goals completed! 🐙Relabelling vertices preserves the chromatic number.
theorem chromaticNumber_map_equiv (G : SimpleGraph V) (e : V ≃ W) :
(G.map e).chromaticNumber = G.chromaticNumber := by V:Type u_1W:Type u_3G:SimpleGraph Ve:V ≃ W⊢ (SimpleGraph.map (⇑e) G).chromaticNumber = G.chromaticNumber
exact le_antisymm
(chromaticNumber_mono_of_hom (Iso.map e G).symm.toHom)
(chromaticNumber_mono_of_hom (Iso.map e G).toHom) All goals completed! 🐙
For every k ≥ 2, a finite graph has clique number two and chromatic number k.
theorem exists_cliqueNum_eq_two_chromaticNumber_eq (k : ℕ) (hk : 2 ≤ k) :
∃ (n : ℕ) (G : SimpleGraph (Fin n)),
G.cliqueNum = 2 ∧ G.chromaticNumber = (k : ℕ∞) := by k:ℕhk:2 ≤ k⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
classical
have hex (j : ℕ) : ∃ (V : Type) (_ : Fintype V) (_ : Nonempty V) (G : SimpleGraph V),
G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ((j + 2 : ℕ) : ℕ∞) := by k:ℕhk:2 ≤ k⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
induction j with
| zero => zero k:ℕhk:2 ≤ k⊢ ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(0 + 2) k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
refine ⟨Fin 2, inferInstance, inferInstance, ⊤, ?_, ?_, by k:ℕhk:2 ≤ k⊢ ⊤.chromaticNumber = ↑(0 + 2) k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k simp All goals completed! 🐙 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k⟩
· zero.refine_1 k:ℕhk:2 ≤ k⊢ ⊤.CliqueFree 3 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k exact cliqueFree_of_chromaticNumber_lt (by k:ℕhk:2 ≤ k⊢ ⊤.chromaticNumber < ↑3 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k simp k:ℕhk:2 ≤ k⊢ 2 < 3 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k; decide All goals completed! 🐙 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k)
· zero.refine_2 k:ℕhk:2 ≤ k⊢ ⊤.cliqueNum = 2 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k apply Nat.le_antisymm zero.refine_2.h₁ k:ℕhk:2 ≤ k⊢ ⊤.cliqueNum ≤ 2zero.refine_2.h₂ k:ℕhk:2 ≤ k⊢ 2 ≤ ⊤.cliqueNum k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
· zero.refine_2.h₁ k:ℕhk:2 ≤ k⊢ ⊤.cliqueNum ≤ 2 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k exact (cliqueFree_of_chromaticNumber_lt (by k:ℕhk:2 ≤ k⊢ ⊤.chromaticNumber < ↑3 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k simp k:ℕhk:2 ≤ k⊢ 2 < 3 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k; decide All goals completed! 🐙 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k) :
(⊤ : SimpleGraph (Fin 2)).CliqueFree 3).cliqueNum_le_two
· zero.refine_2.h₂ k:ℕhk:2 ≤ k⊢ 2 ≤ ⊤.cliqueNum k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k have h : (⊤ : SimpleGraph (Fin 2)).IsClique (Finset.univ : Finset (Fin 2)) :=
by k:ℕhk:2 ≤ k⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k zero.refine_2.h₂ k:ℕhk:2 ≤ kh:⊤.IsClique ↑Finset.univ⊢ 2 ≤ ⊤.cliqueNum k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k simpzero.refine_2.h₂ k:ℕhk:2 ≤ kh:⊤.IsClique ↑Finset.univ⊢ 2 ≤ ⊤.cliqueNum k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑kzero.refine_2.h₂ k:ℕhk:2 ≤ kh:⊤.IsClique ↑Finset.univ⊢ 2 ≤ ⊤.cliqueNum k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
simpa using h.card_le_cliqueNum All goals completed! 🐙 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
| succ j ih => succ k:ℕhk:2 ≤ kj:ℕih:∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 1 + 2) k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
obtain ⟨V, hV, hne, G, htri, _, hχ⟩ := ih succ k:ℕhk:2 ≤ kj:ℕV:TypehV:Fintype Vhne:Nonempty VG:SimpleGraph Vhtri:G.CliqueFree 3left✝:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(j + 2)⊢ ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 1 + 2) k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
let := hV succ k:ℕhk:2 ≤ kj:ℕV:TypehV:Fintype Vhne:Nonempty VG:SimpleGraph Vhtri:G.CliqueFree 3left✝:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(j + 2)this:Fintype V := hV⊢ ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 1 + 2) k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
let := hne succ k:ℕhk:2 ≤ kj:ℕV:TypehV:Fintype Vhne:Nonempty VG:SimpleGraph Vhtri:G.CliqueFree 3left✝:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(j + 2)this✝:Fintype V := hVthis:Nonempty V := ···⊢ ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 1 + 2) k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
refine ⟨Option (V ⊕ V), inferInstance, inferInstance, G.mycielski,
htri.mycielski, cliqueNum_mycielski htri, ?_⟩ succ k:ℕhk:2 ≤ kj:ℕV:TypehV:Fintype Vhne:Nonempty VG:SimpleGraph Vhtri:G.CliqueFree 3left✝:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(j + 2)this✝:Fintype V := hVthis:Nonempty V := ···⊢ G.mycielski.chromaticNumber = ↑(j + 1 + 2) k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
simpa only [Nat.succ_eq_add_one, Nat.add_assoc, Nat.add_comm 1 2] using
chromaticNumber_mycielski hχ k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
obtain ⟨V, hV, _, G, _, hω, hχ⟩ := hex (k - 2) k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)V:TypehV:Fintype Vw✝:Nonempty VG:SimpleGraph Vleft✝:G.CliqueFree 3hω:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(k - 2 + 2)⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
let := hV k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)V:TypehV:Fintype Vw✝:Nonempty VG:SimpleGraph Vleft✝:G.CliqueFree 3hω:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(k - 2 + 2)this:Fintype V := hV⊢ ∃ n G, G.cliqueNum = 2 ∧ G.chromaticNumber = ↑k
refine ⟨Fintype.card V, G.map (Fintype.equivFin V), ?_, ?_⟩ refine_1 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)V:TypehV:Fintype Vw✝:Nonempty VG:SimpleGraph Vleft✝:G.CliqueFree 3hω:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(k - 2 + 2)this:Fintype V := hV⊢ (SimpleGraph.map (⇑(Fintype.equivFin V)) G).cliqueNum = 2refine_2 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)V:TypehV:Fintype Vw✝:Nonempty VG:SimpleGraph Vleft✝:G.CliqueFree 3hω:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(k - 2 + 2)this:Fintype V := hV⊢ (SimpleGraph.map (⇑(Fintype.equivFin V)) G).chromaticNumber = ↑k
· refine_1 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)V:TypehV:Fintype Vw✝:Nonempty VG:SimpleGraph Vleft✝:G.CliqueFree 3hω:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(k - 2 + 2)this:Fintype V := hV⊢ (SimpleGraph.map (⇑(Fintype.equivFin V)) G).cliqueNum = 2 simpa only [cliqueNum_map_equiv] using hω All goals completed! 🐙
· refine_2 k:ℕhk:2 ≤ khex:∀ (j : ℕ), ∃ V x, ∃ (_ : Nonempty V), ∃ G, G.CliqueFree 3 ∧ G.cliqueNum = 2 ∧ G.chromaticNumber = ↑(j + 2)V:TypehV:Fintype Vw✝:Nonempty VG:SimpleGraph Vleft✝:G.CliqueFree 3hω:G.cliqueNum = 2hχ:G.chromaticNumber = ↑(k - 2 + 2)this:Fintype V := hV⊢ (SimpleGraph.map (⇑(Fintype.equivFin V)) G).chromaticNumber = ↑k simpa only [chromaticNumber_map_equiv, Nat.sub_add_cancel hk] using hχ All goals completed! 🐙end SimpleGraph