combinatorics.simple_graph.coloring | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

70fd9563

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

ee05e9ce

bump to nightly-2024-04-06-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

e34029c9

Diff

@@ -435,8 +435,8 @@ theorem SimpleGraph.chromaticNumber_mono_of_embedding {V' : Type _} {G' : Simple
 #align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.chromaticNumber_mono_of_embedding
 -/
 
-#print SimpleGraph.chromaticNumber_eq_card_of_forall_surj /-
-theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
+#print SimpleGraph.chromaticNumber_eq_card_iff_forall_surjective /-
+theorem chromaticNumber_eq_card_iff_forall_surjective [Fintype α] (C : G.Coloring α)
     (h : ∀ C' : G.Coloring α, Function.Surjective C') : G.chromaticNumber = Fintype.card α :=
   by
   apply le_antisymm
@@ -453,7 +453,7 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
     have h1 : Function.Surjective f := Function.Surjective.of_comp h
     have h2 := Fintype.card_le_of_surjective _ h1
     exact Nat.lt_le_asymm hc h2
-#align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_of_forall_surj
+#align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_iff_forall_surjective
 -/
 
 #print SimpleGraph.chromaticNumber_bot /-

ee05e9ce

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -215,7 +215,7 @@ def recolorOfEmbedding {α β : Type _} (f : α ↪ β) : G.Coloring α ↪ G.Co
     by
     -- this was strangely painful; seems like missing lemmas about embeddings
     intro C C' h
-    dsimp only at h 
+    dsimp only at h
     ext v
     apply (embedding.complete_graph f).inj'
     change ((embedding.complete_graph f).toHom.comp C) v = _
@@ -269,7 +269,7 @@ theorem colorable_of_fintype (G : SimpleGraph V) [Fintype V] : G.Colorable (Fint
 noncomputable def Colorable.toColoring [Fintype α] {n : ℕ} (hc : G.Colorable n)
     (hn : n ≤ Fintype.card α) : G.Coloring α :=
   by
-  rw [← Fintype.card_fin n] at hn 
+  rw [← Fintype.card_fin n] at hn
   exact G.recolor_of_card_le hn hc.some
 #align simple_graph.colorable.to_coloring SimpleGraph.Colorable.toColoring
 -/
@@ -376,7 +376,7 @@ theorem isEmpty_of_chromaticNumber_eq_zero (G : SimpleGraph V) [Finite V]
     (h : G.chromaticNumber = 0) : IsEmpty V :=
   by
   have h' := G.colorable_chromatic_number_of_fintype
-  rw [h] at h' 
+  rw [h] at h'
   exact G.is_empty_of_colorable_zero h'
 #align simple_graph.is_empty_of_chromatic_number_eq_zero SimpleGraph.isEmpty_of_chromaticNumber_eq_zero
 -/
@@ -387,7 +387,7 @@ theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.
   apply le_csInf (colorable_set_nonempty_of_colorable hc)
   intro m hm
   by_contra h'
-  simp only [not_le, Nat.lt_one_iff] at h' 
+  simp only [not_le, Nat.lt_one_iff] at h'
   subst h'
   obtain ⟨i, hi⟩ := hm.some (Classical.arbitrary V)
   exact Nat.not_lt_zero _ hi
@@ -442,14 +442,14 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
   apply le_antisymm
   · apply chromatic_number_le_card C
   · by_contra hc
-    rw [not_le] at hc 
+    rw [not_le] at hc
     obtain ⟨n, cn, hc⟩ :=
       exists_lt_of_csInf_lt (colorable_set_nonempty_of_colorable C.to_colorable) hc
-    rw [← Fintype.card_fin n] at hc 
+    rw [← Fintype.card_fin n] at hc
     have f := (Function.Embedding.nonempty_of_card_le (le_of_lt hc)).some
     have C' := cn.some
     specialize h (G.recolor_of_embedding f C')
-    change Function.Surjective (f ∘ C') at h 
+    change Function.Surjective (f ∘ C') at h
     have h1 : Function.Surjective f := Function.Surjective.of_comp h
     have h2 := Fintype.card_le_of_surjective _ h1
     exact Nat.lt_le_asymm hc h2
@@ -522,8 +522,8 @@ theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [None
   · by_cases he' : C (Sum.inr w) = b
     · exact ⟨_, he'⟩
     · exfalso
-      cases b <;> simp only [eq_true_eq_not_eq_false, Bool.eq_false_eq_not_eq_true] at he he'  <;>
-          rw [he, he'] at hn  <;>
+      cases b <;> simp only [eq_true_eq_not_eq_false, Bool.eq_false_eq_not_eq_true] at he he' <;>
+          rw [he, he'] at hn <;>
         contradiction
 #align simple_graph.complete_bipartite_graph.chromatic_number SimpleGraph.CompleteBipartiteGraph.chromaticNumber
 -/
@@ -535,9 +535,9 @@ theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [None
 theorem IsClique.card_le_of_coloring {s : Finset V} (h : G.IsClique s) [Fintype α]
     (C : G.Coloring α) : s.card ≤ Fintype.card α :=
   by
-  rw [is_clique_iff_induce_eq] at h 
+  rw [is_clique_iff_induce_eq] at h
   have f : G.induce ↑s ↪g G := embedding.induce ↑s
-  rw [h] at f 
+  rw [h] at f
   convert Fintype.card_le_of_injective _ (C.comp f.to_hom).injective_of_top_hom using 1
   simp
 #align simple_graph.is_clique.card_le_of_coloring SimpleGraph.IsClique.card_le_of_coloring
@@ -566,7 +566,7 @@ theorem IsClique.card_le_chromaticNumber [Finite V] {s : Finset V} (h : G.IsCliq
 protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n < m) :
     G.CliqueFree m := by
   by_contra h
-  simp only [clique_free, is_n_clique_iff, Classical.not_forall, Classical.not_not] at h 
+  simp only [clique_free, is_n_clique_iff, Classical.not_forall, Classical.not_not] at h
   obtain ⟨s, h, rfl⟩ := h
   exact Nat.lt_le_asymm hm (h.card_le_of_colorable hc)
 #align simple_graph.colorable.clique_free SimpleGraph.Colorable.cliqueFree

ee05e9ce

bump to nightly-2024-02-07-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

8a1bf67e

Diff

@@ -76,7 +76,7 @@ variable {G} {α : Type v} (C : G.Coloring α)
 
 #print SimpleGraph.Coloring.valid /-
 theorem Coloring.valid {v w : V} (h : G.Adj v w) : C v ≠ C w :=
-  C.map_rel h
+  C.mapRel h
 #align simple_graph.coloring.valid SimpleGraph.Coloring.valid
 -/

ee05e9ce

bump to nightly-2024-02-01-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

5433bded

Diff

@@ -153,7 +153,11 @@ theorem Coloring.color_classes_independent (c : α) : IsAntichain G.Adj (C.color
 -/
 
 -- TODO make this computable
-noncomputable instance [Fintype V] [Fintype α] : Fintype (Coloring G α) := by classical
+noncomputable instance [Fintype V] [Fintype α] : Fintype (Coloring G α) := by
+  classical
+  change Fintype (RelHom G.adj (⊤ : SimpleGraph α).Adj)
+  apply Fintype.ofInjective _ RelHom.coe_fn_injective
+  infer_instance
 
 variable (G)

ee05e9ce

bump to nightly-2024-01-31-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

61100fe9

Diff

@@ -153,11 +153,7 @@ theorem Coloring.color_classes_independent (c : α) : IsAntichain G.Adj (C.color
 -/
 
 -- TODO make this computable
-noncomputable instance [Fintype V] [Fintype α] : Fintype (Coloring G α) := by
-  classical
-  change Fintype (RelHom G.adj (⊤ : SimpleGraph α).Adj)
-  apply Fintype.ofInjective _ RelHom.coe_fn_injective
-  infer_instance
+noncomputable instance [Fintype V] [Fintype α] : Fintype (Coloring G α) := by classical
 
 variable (G)

ee05e9ce

bump to nightly-2024-01-17-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

8ba88f37

Diff

@@ -252,15 +252,15 @@ theorem Colorable.mono {n m : ℕ} (h : n ≤ m) (hc : G.Colorable n) : G.Colora
 #align simple_graph.colorable.mono SimpleGraph.Colorable.mono
 -/
 
-#print SimpleGraph.Coloring.to_colorable /-
-theorem Coloring.to_colorable [Fintype α] (C : G.Coloring α) : G.Colorable (Fintype.card α) :=
+#print SimpleGraph.Coloring.colorable /-
+theorem Coloring.colorable [Fintype α] (C : G.Coloring α) : G.Colorable (Fintype.card α) :=
   ⟨G.recolorOfCardLE (by simp) C⟩
-#align simple_graph.coloring.to_colorable SimpleGraph.Coloring.to_colorable
+#align simple_graph.coloring.to_colorable SimpleGraph.Coloring.colorable
 -/
 
 #print SimpleGraph.colorable_of_fintype /-
 theorem colorable_of_fintype (G : SimpleGraph V) [Fintype V] : G.Colorable (Fintype.card V) :=
-  G.selfColoring.to_colorable
+  G.selfColoring.colorable
 #align simple_graph.colorable_of_fintype SimpleGraph.colorable_of_fintype
 -/
 
@@ -315,20 +315,20 @@ theorem chromaticNumber_bddBelow : BddBelow {n : ℕ | G.Colorable n} :=
 #align simple_graph.chromatic_number_bdd_below SimpleGraph.chromaticNumber_bddBelow
 -/
 
-#print SimpleGraph.chromaticNumber_le_of_colorable /-
-theorem chromaticNumber_le_of_colorable {n : ℕ} (hc : G.Colorable n) : G.chromaticNumber ≤ n :=
-  by
+#print SimpleGraph.Colorable.chromaticNumber_le /-
+theorem SimpleGraph.Colorable.chromaticNumber_le {n : ℕ} (hc : G.Colorable n) :
+    G.chromaticNumber ≤ n := by
   rw [chromatic_number]
   apply csInf_le chromatic_number_bdd_below
   fconstructor
   exact Classical.choice hc
-#align simple_graph.chromatic_number_le_of_colorable SimpleGraph.chromaticNumber_le_of_colorable
+#align simple_graph.chromatic_number_le_of_colorable SimpleGraph.Colorable.chromaticNumber_le
 -/
 
 #print SimpleGraph.chromaticNumber_le_card /-
 theorem chromaticNumber_le_card [Fintype α] (C : G.Coloring α) :
     G.chromaticNumber ≤ Fintype.card α :=
-  csInf_le chromaticNumber_bddBelow C.to_colorable
+  csInf_le chromaticNumber_bddBelow C.colorable
 #align simple_graph.chromatic_number_le_card SimpleGraph.chromaticNumber_le_card
 -/
 
@@ -394,13 +394,13 @@ theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.
 #align simple_graph.chromatic_number_pos SimpleGraph.chromaticNumber_pos
 -/
 
-#print SimpleGraph.colorable_of_chromaticNumber_pos /-
-theorem colorable_of_chromaticNumber_pos (h : 0 < G.chromaticNumber) :
+#print SimpleGraph.colorable_of_chromaticNumber_ne_top /-
+theorem colorable_of_chromaticNumber_ne_top (h : 0 < G.chromaticNumber) :
     G.Colorable G.chromaticNumber :=
   by
   obtain ⟨h, hn⟩ := Nat.nonempty_of_pos_sInf h
   exact colorable_chromatic_number hn
-#align simple_graph.colorable_of_chromatic_number_pos SimpleGraph.colorable_of_chromaticNumber_pos
+#align simple_graph.colorable_of_chromatic_number_pos SimpleGraph.colorable_of_chromaticNumber_ne_top
 -/
 
 #print SimpleGraph.Colorable.mono_left /-
@@ -410,29 +410,29 @@ theorem Colorable.mono_left {G' : SimpleGraph V} (h : G ≤ G') {n : ℕ} (hc :
 #align simple_graph.colorable.mono_left SimpleGraph.Colorable.mono_left
 -/
 
-#print SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp /-
-theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGraph V'} {m : ℕ}
+#print SimpleGraph.chromaticNumber_le_of_forall_imp /-
+theorem SimpleGraph.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGraph V'} {m : ℕ}
     (hc : G'.Colorable m) (h : ∀ n, G'.Colorable n → G.Colorable n) :
     G.chromaticNumber ≤ G'.chromaticNumber :=
   by
   apply csInf_le chromatic_number_bdd_below
   apply h
   apply colorable_chromatic_number hc
-#align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp
+#align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.chromaticNumber_le_of_forall_imp
 -/
 
-#print SimpleGraph.Colorable.chromaticNumber_mono /-
-theorem Colorable.chromaticNumber_mono (G' : SimpleGraph V) {m : ℕ} (hc : G'.Colorable m)
+#print SimpleGraph.chromaticNumber_mono /-
+theorem SimpleGraph.chromaticNumber_mono (G' : SimpleGraph V) {m : ℕ} (hc : G'.Colorable m)
     (h : G ≤ G') : G.chromaticNumber ≤ G'.chromaticNumber :=
   hc.chromaticNumber_le_of_forall_imp fun n => Colorable.mono_left h
-#align simple_graph.colorable.chromatic_number_mono SimpleGraph.Colorable.chromaticNumber_mono
+#align simple_graph.colorable.chromatic_number_mono SimpleGraph.chromaticNumber_mono
 -/
 
-#print SimpleGraph.Colorable.chromaticNumber_mono_of_embedding /-
-theorem Colorable.chromaticNumber_mono_of_embedding {V' : Type _} {G' : SimpleGraph V'} {n : ℕ}
+#print SimpleGraph.chromaticNumber_mono_of_embedding /-
+theorem SimpleGraph.chromaticNumber_mono_of_embedding {V' : Type _} {G' : SimpleGraph V'} {n : ℕ}
     (h : G'.Colorable n) (f : G ↪g G') : G.chromaticNumber ≤ G'.chromaticNumber :=
   h.chromaticNumber_le_of_forall_imp fun _ => Colorable.of_embedding f
-#align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.Colorable.chromaticNumber_mono_of_embedding
+#align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.chromaticNumber_mono_of_embedding
 -/
 
 #print SimpleGraph.chromaticNumber_eq_card_of_forall_surj /-
@@ -480,8 +480,8 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
 #align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_top
 -/
 
-#print SimpleGraph.chromaticNumber_top_eq_zero_of_infinite /-
-theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
+#print SimpleGraph.chromaticNumber_top_eq_top_of_infinite /-
+theorem chromaticNumber_top_eq_top_of_infinite (V : Type _) [Infinite V] :
     (⊤ : SimpleGraph V).chromaticNumber = 0 :=
   by
   let n := (⊤ : SimpleGraph V).chromaticNumber
@@ -493,7 +493,7 @@ theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
   refine' (colorable_of_chromatic_number_pos hc).chromaticNumber_mono_of_embedding _
   apply embedding.complete_graph
   exact (Function.Embedding.subtype _).trans (Infinite.natEmbedding V)
-#align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_zero_of_infinite
+#align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_top_of_infinite
 -/
 
 #print SimpleGraph.CompleteBipartiteGraph.bicoloring /-

ee05e9ce

bump to nightly-2023-11-06-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

f9f7c90b

Diff

@@ -452,7 +452,7 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
     change Function.Surjective (f ∘ C') at h 
     have h1 : Function.Surjective f := Function.Surjective.of_comp h
     have h2 := Fintype.card_le_of_surjective _ h1
-    exact Nat.lt_le_antisymm hc h2
+    exact Nat.lt_le_asymm hc h2
 #align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_of_forall_surj
 -/
 
@@ -568,7 +568,7 @@ protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n
   by_contra h
   simp only [clique_free, is_n_clique_iff, Classical.not_forall, Classical.not_not] at h 
   obtain ⟨s, h, rfl⟩ := h
-  exact Nat.lt_le_antisymm hm (h.card_le_of_colorable hc)
+  exact Nat.lt_le_asymm hm (h.card_le_of_colorable hc)
 #align simple_graph.colorable.clique_free SimpleGraph.Colorable.cliqueFree
 -/

ee05e9ce

bump to nightly-2023-10-21-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/b1abe23ae96fef89ad30d9f4362c307f72a55010

a2dc86f8

Diff

@@ -566,7 +566,7 @@ theorem IsClique.card_le_chromaticNumber [Finite V] {s : Finset V} (h : G.IsCliq
 protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n < m) :
     G.CliqueFree m := by
   by_contra h
-  simp only [clique_free, is_n_clique_iff, not_forall, Classical.not_not] at h 
+  simp only [clique_free, is_n_clique_iff, Classical.not_forall, Classical.not_not] at h 
   obtain ⟨s, h, rfl⟩ := h
   exact Nat.lt_le_antisymm hm (h.card_le_of_colorable hc)
 #align simple_graph.colorable.clique_free SimpleGraph.Colorable.cliqueFree

ee05e9ce

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2021 Arthur Paulino. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
 -/
-import Mathbin.Combinatorics.SimpleGraph.Clique
-import Mathbin.Data.Nat.Lattice
-import Mathbin.Data.Setoid.Partition
-import Mathbin.Order.Antichain
+import Combinatorics.SimpleGraph.Clique
+import Data.Nat.Lattice
+import Data.Setoid.Partition
+import Order.Antichain
 
 #align_import combinatorics.simple_graph.coloring from "leanprover-community/mathlib"@"ee05e9ce1322178f0c12004eb93c00d2c8c00ed2"

ee05e9ce

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2021 Arthur Paulino. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.coloring
-! leanprover-community/mathlib commit ee05e9ce1322178f0c12004eb93c00d2c8c00ed2
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Combinatorics.SimpleGraph.Clique
 import Mathbin.Data.Nat.Lattice
 import Mathbin.Data.Setoid.Partition
 import Mathbin.Order.Antichain
 
+#align_import combinatorics.simple_graph.coloring from "leanprover-community/mathlib"@"ee05e9ce1322178f0c12004eb93c00d2c8c00ed2"
+
 /-!
 # Graph Coloring

ee05e9ce

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -277,10 +277,12 @@ noncomputable def Colorable.toColoring [Fintype α] {n : ℕ} (hc : G.Colorable
 #align simple_graph.colorable.to_coloring SimpleGraph.Colorable.toColoring
 -/
 
+#print SimpleGraph.Colorable.of_embedding /-
 theorem Colorable.of_embedding {V' : Type _} {G' : SimpleGraph V'} (f : G ↪g G') {n : ℕ}
     (h : G'.Colorable n) : G.Colorable n :=
   ⟨(h.toColoring (by simp)).comp f⟩
 #align simple_graph.colorable.of_embedding SimpleGraph.Colorable.of_embedding
+-/
 
 #print SimpleGraph.colorable_iff_exists_bdd_nat_coloring /-
 theorem colorable_iff_exists_bdd_nat_coloring (n : ℕ) :
@@ -411,6 +413,7 @@ theorem Colorable.mono_left {G' : SimpleGraph V} (h : G ≤ G') {n : ℕ} (hc :
 #align simple_graph.colorable.mono_left SimpleGraph.Colorable.mono_left
 -/
 
+#print SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp /-
 theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGraph V'} {m : ℕ}
     (hc : G'.Colorable m) (h : ∀ n, G'.Colorable n → G.Colorable n) :
     G.chromaticNumber ≤ G'.chromaticNumber :=
@@ -419,6 +422,7 @@ theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGra
   apply h
   apply colorable_chromatic_number hc
 #align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp
+-/
 
 #print SimpleGraph.Colorable.chromaticNumber_mono /-
 theorem Colorable.chromaticNumber_mono (G' : SimpleGraph V) {m : ℕ} (hc : G'.Colorable m)
@@ -427,10 +431,12 @@ theorem Colorable.chromaticNumber_mono (G' : SimpleGraph V) {m : ℕ} (hc : G'.C
 #align simple_graph.colorable.chromatic_number_mono SimpleGraph.Colorable.chromaticNumber_mono
 -/
 
+#print SimpleGraph.Colorable.chromaticNumber_mono_of_embedding /-
 theorem Colorable.chromaticNumber_mono_of_embedding {V' : Type _} {G' : SimpleGraph V'} {n : ℕ}
     (h : G'.Colorable n) (f : G ↪g G') : G.chromaticNumber ≤ G'.chromaticNumber :=
   h.chromaticNumber_le_of_forall_imp fun _ => Colorable.of_embedding f
 #align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.Colorable.chromaticNumber_mono_of_embedding
+-/
 
 #print SimpleGraph.chromaticNumber_eq_card_of_forall_surj /-
 theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
@@ -453,6 +459,7 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
 #align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_of_forall_surj
 -/
 
+#print SimpleGraph.chromaticNumber_bot /-
 theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber = 1 :=
   by
   let C : (⊥ : SimpleGraph V).Coloring (Fin 1) := coloring.mk (fun _ => 0) fun v w h => False.elim h
@@ -460,7 +467,9 @@ theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber
   · exact chromatic_number_le_card C
   · exact chromatic_number_pos C.to_colorable
 #align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_bot
+-/
 
+#print SimpleGraph.chromaticNumber_top /-
 @[simp]
 theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber = Fintype.card V :=
   by
@@ -472,7 +481,9 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
   intro h
   exact C.valid h
 #align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_top
+-/
 
+#print SimpleGraph.chromaticNumber_top_eq_zero_of_infinite /-
 theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
     (⊤ : SimpleGraph V).chromaticNumber = 0 :=
   by
@@ -486,6 +497,7 @@ theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
   apply embedding.complete_graph
   exact (Function.Embedding.subtype _).trans (Infinite.natEmbedding V)
 #align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_zero_of_infinite
+-/
 
 #print SimpleGraph.CompleteBipartiteGraph.bicoloring /-
 /-- The bicoloring of a complete bipartite graph using whether a vertex
@@ -498,6 +510,7 @@ def CompleteBipartiteGraph.bicoloring (V W : Type _) : (completeBipartiteGraph V
 #align simple_graph.complete_bipartite_graph.bicoloring SimpleGraph.CompleteBipartiteGraph.bicoloring
 -/
 
+#print SimpleGraph.CompleteBipartiteGraph.chromaticNumber /-
 theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [Nonempty W] :
     (completeBipartiteGraph V W).chromaticNumber = 2 :=
   by
@@ -516,6 +529,7 @@ theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [None
           rw [he, he'] at hn  <;>
         contradiction
 #align simple_graph.complete_bipartite_graph.chromatic_number SimpleGraph.CompleteBipartiteGraph.chromaticNumber
+-/
 
 /-! ### Cliques -/

ee05e9ce

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -101,7 +101,7 @@ def Coloring.mk (color : V → α) (valid : ∀ {v w : V}, G.Adj v w → color v
 /-- The color class of a given color.
 -/
 def Coloring.colorClass (c : α) : Set V :=
-  { v : V | C v = c }
+  {v : V | C v = c}
 #align simple_graph.coloring.color_class SimpleGraph.Coloring.colorClass
 -/
 
@@ -158,9 +158,9 @@ theorem Coloring.color_classes_independent (c : α) : IsAntichain G.Adj (C.color
 -- TODO make this computable
 noncomputable instance [Fintype V] [Fintype α] : Fintype (Coloring G α) := by
   classical
-    change Fintype (RelHom G.adj (⊤ : SimpleGraph α).Adj)
-    apply Fintype.ofInjective _ RelHom.coe_fn_injective
-    infer_instance
+  change Fintype (RelHom G.adj (⊤ : SimpleGraph α).Adj)
+  apply Fintype.ofInjective _ RelHom.coe_fn_injective
+  infer_instance
 
 variable (G)
 
@@ -205,7 +205,7 @@ def selfColoring : G.Coloring V :=
 /-- The chromatic number of a graph is the minimal number of colors needed to color it.
 If `G` isn't colorable with finitely many colors, this will be 0. -/
 noncomputable def chromaticNumber : ℕ :=
-  sInf { n : ℕ | G.Colorable n }
+  sInf {n : ℕ | G.Colorable n}
 #align simple_graph.chromatic_number SimpleGraph.chromaticNumber
 -/
 
@@ -305,13 +305,13 @@ theorem colorable_iff_exists_bdd_nat_coloring (n : ℕ) :
 
 #print SimpleGraph.colorable_set_nonempty_of_colorable /-
 theorem colorable_set_nonempty_of_colorable {n : ℕ} (hc : G.Colorable n) :
-    { n : ℕ | G.Colorable n }.Nonempty :=
+    {n : ℕ | G.Colorable n}.Nonempty :=
   ⟨n, hc⟩
 #align simple_graph.colorable_set_nonempty_of_colorable SimpleGraph.colorable_set_nonempty_of_colorable
 -/
 
 #print SimpleGraph.chromaticNumber_bddBelow /-
-theorem chromaticNumber_bddBelow : BddBelow { n : ℕ | G.Colorable n } :=
+theorem chromaticNumber_bddBelow : BddBelow {n : ℕ | G.Colorable n} :=
   ⟨0, fun _ _ => zero_le _⟩
 #align simple_graph.chromatic_number_bdd_below SimpleGraph.chromaticNumber_bddBelow
 -/
@@ -480,7 +480,7 @@ theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
   by_contra hc
   replace hc := pos_iff_ne_zero.mpr hc
   apply Nat.not_succ_le_self n
-  convert_to(⊤ : SimpleGraph { m | m < n + 1 }).chromaticNumber ≤ _
+  convert_to (⊤ : SimpleGraph {m | m < n + 1}).chromaticNumber ≤ _
   · simp
   refine' (colorable_of_chromatic_number_pos hc).chromaticNumber_mono_of_embedding _
   apply embedding.complete_graph

ee05e9ce

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -218,7 +218,7 @@ def recolorOfEmbedding {α β : Type _} (f : α ↪ β) : G.Coloring α ↪ G.Co
     by
     -- this was strangely painful; seems like missing lemmas about embeddings
     intro C C' h
-    dsimp only at h
+    dsimp only at h 
     ext v
     apply (embedding.complete_graph f).inj'
     change ((embedding.complete_graph f).toHom.comp C) v = _
@@ -272,7 +272,7 @@ theorem colorable_of_fintype (G : SimpleGraph V) [Fintype V] : G.Colorable (Fint
 noncomputable def Colorable.toColoring [Fintype α] {n : ℕ} (hc : G.Colorable n)
     (hn : n ≤ Fintype.card α) : G.Coloring α :=
   by
-  rw [← Fintype.card_fin n] at hn
+  rw [← Fintype.card_fin n] at hn 
   exact G.recolor_of_card_le hn hc.some
 #align simple_graph.colorable.to_coloring SimpleGraph.Colorable.toColoring
 -/
@@ -377,7 +377,7 @@ theorem isEmpty_of_chromaticNumber_eq_zero (G : SimpleGraph V) [Finite V]
     (h : G.chromaticNumber = 0) : IsEmpty V :=
   by
   have h' := G.colorable_chromatic_number_of_fintype
-  rw [h] at h'
+  rw [h] at h' 
   exact G.is_empty_of_colorable_zero h'
 #align simple_graph.is_empty_of_chromatic_number_eq_zero SimpleGraph.isEmpty_of_chromaticNumber_eq_zero
 -/
@@ -388,7 +388,7 @@ theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.
   apply le_csInf (colorable_set_nonempty_of_colorable hc)
   intro m hm
   by_contra h'
-  simp only [not_le, Nat.lt_one_iff] at h'
+  simp only [not_le, Nat.lt_one_iff] at h' 
   subst h'
   obtain ⟨i, hi⟩ := hm.some (Classical.arbitrary V)
   exact Nat.not_lt_zero _ hi
@@ -439,14 +439,14 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
   apply le_antisymm
   · apply chromatic_number_le_card C
   · by_contra hc
-    rw [not_le] at hc
+    rw [not_le] at hc 
     obtain ⟨n, cn, hc⟩ :=
       exists_lt_of_csInf_lt (colorable_set_nonempty_of_colorable C.to_colorable) hc
-    rw [← Fintype.card_fin n] at hc
+    rw [← Fintype.card_fin n] at hc 
     have f := (Function.Embedding.nonempty_of_card_le (le_of_lt hc)).some
     have C' := cn.some
     specialize h (G.recolor_of_embedding f C')
-    change Function.Surjective (f ∘ C') at h
+    change Function.Surjective (f ∘ C') at h 
     have h1 : Function.Surjective f := Function.Surjective.of_comp h
     have h2 := Fintype.card_le_of_surjective _ h1
     exact Nat.lt_le_antisymm hc h2
@@ -512,8 +512,8 @@ theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [None
   · by_cases he' : C (Sum.inr w) = b
     · exact ⟨_, he'⟩
     · exfalso
-      cases b <;> simp only [eq_true_eq_not_eq_false, Bool.eq_false_eq_not_eq_true] at he he' <;>
-          rw [he, he'] at hn <;>
+      cases b <;> simp only [eq_true_eq_not_eq_false, Bool.eq_false_eq_not_eq_true] at he he'  <;>
+          rw [he, he'] at hn  <;>
         contradiction
 #align simple_graph.complete_bipartite_graph.chromatic_number SimpleGraph.CompleteBipartiteGraph.chromaticNumber
 
@@ -524,9 +524,9 @@ theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [None
 theorem IsClique.card_le_of_coloring {s : Finset V} (h : G.IsClique s) [Fintype α]
     (C : G.Coloring α) : s.card ≤ Fintype.card α :=
   by
-  rw [is_clique_iff_induce_eq] at h
+  rw [is_clique_iff_induce_eq] at h 
   have f : G.induce ↑s ↪g G := embedding.induce ↑s
-  rw [h] at f
+  rw [h] at f 
   convert Fintype.card_le_of_injective _ (C.comp f.to_hom).injective_of_top_hom using 1
   simp
 #align simple_graph.is_clique.card_le_of_coloring SimpleGraph.IsClique.card_le_of_coloring
@@ -555,7 +555,7 @@ theorem IsClique.card_le_chromaticNumber [Finite V] {s : Finset V} (h : G.IsCliq
 protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n < m) :
     G.CliqueFree m := by
   by_contra h
-  simp only [clique_free, is_n_clique_iff, not_forall, Classical.not_not] at h
+  simp only [clique_free, is_n_clique_iff, not_forall, Classical.not_not] at h 
   obtain ⟨s, h, rfl⟩ := h
   exact Nat.lt_le_antisymm hm (h.card_le_of_colorable hc)
 #align simple_graph.colorable.clique_free SimpleGraph.Colorable.cliqueFree

ee05e9ce

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -277,12 +277,6 @@ noncomputable def Colorable.toColoring [Fintype α] {n : ℕ} (hc : G.Colorable
 #align simple_graph.colorable.to_coloring SimpleGraph.Colorable.toColoring
 -/
 
-/- warning: simple_graph.colorable.of_embedding -> SimpleGraph.Colorable.of_embedding is a dubious translation:
-lean 3 declaration is
-  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {V' : Type.{u2}} {G' : SimpleGraph.{u2} V'}, (SimpleGraph.Embedding.{u1, u2} V V' G G') -> (forall {n : Nat}, (SimpleGraph.Colorable.{u2} V' G' n) -> (SimpleGraph.Colorable.{u1} V G n))
-but is expected to have type
-  forall {V : Type.{u2}} {G : SimpleGraph.{u2} V} {V' : Type.{u1}} {G' : SimpleGraph.{u1} V'}, (SimpleGraph.Embedding.{u2, u1} V V' G G') -> (forall {n : Nat}, (SimpleGraph.Colorable.{u1} V' G' n) -> (SimpleGraph.Colorable.{u2} V G n))
-Case conversion may be inaccurate. Consider using '#align simple_graph.colorable.of_embedding SimpleGraph.Colorable.of_embeddingₓ'. -/
 theorem Colorable.of_embedding {V' : Type _} {G' : SimpleGraph V'} (f : G ↪g G') {n : ℕ}
     (h : G'.Colorable n) : G.Colorable n :=
   ⟨(h.toColoring (by simp)).comp f⟩
@@ -417,12 +411,6 @@ theorem Colorable.mono_left {G' : SimpleGraph V} (h : G ≤ G') {n : ℕ} (hc :
 #align simple_graph.colorable.mono_left SimpleGraph.Colorable.mono_left
 -/
 
-/- warning: simple_graph.colorable.chromatic_number_le_of_forall_imp -> SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp is a dubious translation:
-lean 3 declaration is
-  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {V' : Type.{u2}} {G' : SimpleGraph.{u2} V'} {m : Nat}, (SimpleGraph.Colorable.{u2} V' G' m) -> (forall (n : Nat), (SimpleGraph.Colorable.{u2} V' G' n) -> (SimpleGraph.Colorable.{u1} V G n)) -> (LE.le.{0} Nat Nat.hasLe (SimpleGraph.chromaticNumber.{u1} V G) (SimpleGraph.chromaticNumber.{u2} V' G'))
-but is expected to have type
-  forall {V : Type.{u2}} {G : SimpleGraph.{u2} V} {V' : Type.{u1}} {G' : SimpleGraph.{u1} V'} {m : Nat}, (SimpleGraph.Colorable.{u1} V' G' m) -> (forall (n : Nat), (SimpleGraph.Colorable.{u1} V' G' n) -> (SimpleGraph.Colorable.{u2} V G n)) -> (LE.le.{0} Nat instLENat (SimpleGraph.chromaticNumber.{u2} V G) (SimpleGraph.chromaticNumber.{u1} V' G'))
-Case conversion may be inaccurate. Consider using '#align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.Colorable.chromaticNumber_le_of_forall_impₓ'. -/
 theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGraph V'} {m : ℕ}
     (hc : G'.Colorable m) (h : ∀ n, G'.Colorable n → G.Colorable n) :
     G.chromaticNumber ≤ G'.chromaticNumber :=
@@ -439,12 +427,6 @@ theorem Colorable.chromaticNumber_mono (G' : SimpleGraph V) {m : ℕ} (hc : G'.C
 #align simple_graph.colorable.chromatic_number_mono SimpleGraph.Colorable.chromaticNumber_mono
 -/
 
-/- warning: simple_graph.colorable.chromatic_number_mono_of_embedding -> SimpleGraph.Colorable.chromaticNumber_mono_of_embedding is a dubious translation:
-lean 3 declaration is
-  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {V' : Type.{u2}} {G' : SimpleGraph.{u2} V'} {n : Nat}, (SimpleGraph.Colorable.{u2} V' G' n) -> (SimpleGraph.Embedding.{u1, u2} V V' G G') -> (LE.le.{0} Nat Nat.hasLe (SimpleGraph.chromaticNumber.{u1} V G) (SimpleGraph.chromaticNumber.{u2} V' G'))
-but is expected to have type
-  forall {V : Type.{u2}} {G : SimpleGraph.{u2} V} {V' : Type.{u1}} {G' : SimpleGraph.{u1} V'} {n : Nat}, (SimpleGraph.Colorable.{u1} V' G' n) -> (SimpleGraph.Embedding.{u2, u1} V V' G G') -> (LE.le.{0} Nat instLENat (SimpleGraph.chromaticNumber.{u2} V G) (SimpleGraph.chromaticNumber.{u1} V' G'))
-Case conversion may be inaccurate. Consider using '#align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.Colorable.chromaticNumber_mono_of_embeddingₓ'. -/
 theorem Colorable.chromaticNumber_mono_of_embedding {V' : Type _} {G' : SimpleGraph V'} {n : ℕ}
     (h : G'.Colorable n) (f : G ↪g G') : G.chromaticNumber ≤ G'.chromaticNumber :=
   h.chromaticNumber_le_of_forall_imp fun _ => Colorable.of_embedding f
@@ -471,12 +453,6 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
 #align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_of_forall_surj
 -/
 
-/- warning: simple_graph.chromatic_number_bot -> SimpleGraph.chromaticNumber_bot is a dubious translation:
-lean 3 declaration is
-  forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))
-but is expected to have type
-  forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))
-Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_botₓ'. -/
 theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber = 1 :=
   by
   let C : (⊥ : SimpleGraph V).Coloring (Fin 1) := coloring.mk (fun _ => 0) fun v w h => False.elim h
@@ -485,12 +461,6 @@ theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber
   · exact chromatic_number_pos C.to_colorable
 #align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_bot
 
-/- warning: simple_graph.chromatic_number_top -> SimpleGraph.chromaticNumber_top is a dubious translation:
-lean 3 declaration is
-  forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (Fintype.card.{u1} V _inst_1)
-but is expected to have type
-  forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (Fintype.card.{u1} V _inst_1)
-Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_topₓ'. -/
 @[simp]
 theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber = Fintype.card V :=
   by
@@ -503,12 +473,6 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
   exact C.valid h
 #align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_top
 
-/- warning: simple_graph.chromatic_number_top_eq_zero_of_infinite -> SimpleGraph.chromaticNumber_top_eq_zero_of_infinite is a dubious translation:
-lean 3 declaration is
-  forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))
-but is expected to have type
-  forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))
-Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_zero_of_infiniteₓ'. -/
 theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
     (⊤ : SimpleGraph V).chromaticNumber = 0 :=
   by
@@ -534,12 +498,6 @@ def CompleteBipartiteGraph.bicoloring (V W : Type _) : (completeBipartiteGraph V
 #align simple_graph.complete_bipartite_graph.bicoloring SimpleGraph.CompleteBipartiteGraph.bicoloring
 -/
 
-/- warning: simple_graph.complete_bipartite_graph.chromatic_number -> SimpleGraph.CompleteBipartiteGraph.chromaticNumber is a dubious translation:
-lean 3 declaration is
-  forall {V : Type.{u1}} {W : Type.{u2}} [_inst_1 : Nonempty.{succ u1} V] [_inst_2 : Nonempty.{succ u2} W], Eq.{1} Nat (SimpleGraph.chromaticNumber.{max u1 u2} (Sum.{u1, u2} V W) (completeBipartiteGraph.{u1, u2} V W)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))
-but is expected to have type
-  forall {V : Type.{u2}} {W : Type.{u1}} [_inst_1 : Nonempty.{succ u2} V] [_inst_2 : Nonempty.{succ u1} W], Eq.{1} Nat (SimpleGraph.chromaticNumber.{max u2 u1} (Sum.{u2, u1} V W) (completeBipartiteGraph.{u2, u1} V W)) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))
-Case conversion may be inaccurate. Consider using '#align simple_graph.complete_bipartite_graph.chromatic_number SimpleGraph.CompleteBipartiteGraph.chromaticNumberₓ'. -/
 theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [Nonempty W] :
     (completeBipartiteGraph V W).chromaticNumber = 2 :=
   by

ee05e9ce

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -233,12 +233,8 @@ def recolorOfEquiv {α β : Type _} (f : α ≃ β) : G.Coloring α ≃ G.Colori
     where
   toFun := G.recolorOfEmbedding f.toEmbedding
   invFun := G.recolorOfEmbedding f.symm.toEmbedding
-  left_inv C := by
-    ext v
-    apply Equiv.symm_apply_apply
-  right_inv C := by
-    ext v
-    apply Equiv.apply_symm_apply
+  left_inv C := by ext v; apply Equiv.symm_apply_apply
+  right_inv C := by ext v; apply Equiv.apply_symm_apply
 #align simple_graph.recolor_of_equiv SimpleGraph.recolorOfEquiv
 -/
 
@@ -355,8 +351,7 @@ theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) : G.Colorable G
 
 #print SimpleGraph.colorable_chromaticNumber_of_fintype /-
 theorem colorable_chromaticNumber_of_fintype (G : SimpleGraph V) [Finite V] :
-    G.Colorable G.chromaticNumber := by
-  cases nonempty_fintype V
+    G.Colorable G.chromaticNumber := by cases nonempty_fintype V;
   exact colorable_chromatic_number G.colorable_of_fintype
 #align simple_graph.colorable_chromatic_number_of_fintype SimpleGraph.colorable_chromaticNumber_of_fintype
 -/

ee05e9ce

bump to nightly-2023-05-14-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/e3fb84046afd187b710170887195d50bada934ee

d31da313

Diff

@@ -205,7 +205,7 @@ def selfColoring : G.Coloring V :=
 /-- The chromatic number of a graph is the minimal number of colors needed to color it.
 If `G` isn't colorable with finitely many colors, this will be 0. -/
 noncomputable def chromaticNumber : ℕ :=
-  infₛ { n : ℕ | G.Colorable n }
+  sInf { n : ℕ | G.Colorable n }
 #align simple_graph.chromatic_number SimpleGraph.chromaticNumber
 -/
 
@@ -330,7 +330,7 @@ theorem chromaticNumber_bddBelow : BddBelow { n : ℕ | G.Colorable n } :=
 theorem chromaticNumber_le_of_colorable {n : ℕ} (hc : G.Colorable n) : G.chromaticNumber ≤ n :=
   by
   rw [chromatic_number]
-  apply cinfₛ_le chromatic_number_bdd_below
+  apply csInf_le chromatic_number_bdd_below
   fconstructor
   exact Classical.choice hc
 #align simple_graph.chromatic_number_le_of_colorable SimpleGraph.chromaticNumber_le_of_colorable
@@ -339,7 +339,7 @@ theorem chromaticNumber_le_of_colorable {n : ℕ} (hc : G.Colorable n) : G.chrom
 #print SimpleGraph.chromaticNumber_le_card /-
 theorem chromaticNumber_le_card [Fintype α] (C : G.Coloring α) :
     G.chromaticNumber ≤ Fintype.card α :=
-  cinfₛ_le chromaticNumber_bddBelow C.to_colorable
+  csInf_le chromaticNumber_bddBelow C.to_colorable
 #align simple_graph.chromatic_number_le_card SimpleGraph.chromaticNumber_le_card
 -/
 
@@ -347,7 +347,7 @@ theorem chromaticNumber_le_card [Fintype α] (C : G.Coloring α) :
 theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) : G.Colorable G.chromaticNumber :=
   by
   dsimp only [chromatic_number]
-  rw [Nat.infₛ_def]
+  rw [Nat.sInf_def]
   apply Nat.find_spec
   exact colorable_set_nonempty_of_colorable hc
 #align simple_graph.colorable_chromatic_number SimpleGraph.colorable_chromaticNumber
@@ -365,7 +365,7 @@ theorem colorable_chromaticNumber_of_fintype (G : SimpleGraph V) [Finite V] :
 theorem chromaticNumber_le_one_of_subsingleton (G : SimpleGraph V) [Subsingleton V] :
     G.chromaticNumber ≤ 1 := by
   rw [chromatic_number]
-  apply cinfₛ_le chromatic_number_bdd_below
+  apply csInf_le chromatic_number_bdd_below
   fconstructor
   refine' coloring.mk (fun _ => 0) _
   intro v w
@@ -378,7 +378,7 @@ theorem chromaticNumber_le_one_of_subsingleton (G : SimpleGraph V) [Subsingleton
 theorem chromaticNumber_eq_zero_of_isempty (G : SimpleGraph V) [IsEmpty V] :
     G.chromaticNumber = 0 := by
   rw [← nonpos_iff_eq_zero]
-  apply cinfₛ_le chromatic_number_bdd_below
+  apply csInf_le chromatic_number_bdd_below
   apply colorable_of_is_empty
 #align simple_graph.chromatic_number_eq_zero_of_isempty SimpleGraph.chromaticNumber_eq_zero_of_isempty
 -/
@@ -396,7 +396,7 @@ theorem isEmpty_of_chromaticNumber_eq_zero (G : SimpleGraph V) [Finite V]
 #print SimpleGraph.chromaticNumber_pos /-
 theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.chromaticNumber :=
   by
-  apply le_cinfₛ (colorable_set_nonempty_of_colorable hc)
+  apply le_csInf (colorable_set_nonempty_of_colorable hc)
   intro m hm
   by_contra h'
   simp only [not_le, Nat.lt_one_iff] at h'
@@ -410,7 +410,7 @@ theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.
 theorem colorable_of_chromaticNumber_pos (h : 0 < G.chromaticNumber) :
     G.Colorable G.chromaticNumber :=
   by
-  obtain ⟨h, hn⟩ := Nat.nonempty_of_pos_infₛ h
+  obtain ⟨h, hn⟩ := Nat.nonempty_of_pos_sInf h
   exact colorable_chromatic_number hn
 #align simple_graph.colorable_of_chromatic_number_pos SimpleGraph.colorable_of_chromaticNumber_pos
 -/
@@ -432,7 +432,7 @@ theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGra
     (hc : G'.Colorable m) (h : ∀ n, G'.Colorable n → G.Colorable n) :
     G.chromaticNumber ≤ G'.chromaticNumber :=
   by
-  apply cinfₛ_le chromatic_number_bdd_below
+  apply csInf_le chromatic_number_bdd_below
   apply h
   apply colorable_chromatic_number hc
 #align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp
@@ -464,7 +464,7 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
   · by_contra hc
     rw [not_le] at hc
     obtain ⟨n, cn, hc⟩ :=
-      exists_lt_of_cinfₛ_lt (colorable_set_nonempty_of_colorable C.to_colorable) hc
+      exists_lt_of_csInf_lt (colorable_set_nonempty_of_colorable C.to_colorable) hc
     rw [← Fintype.card_fin n] at hc
     have f := (Function.Embedding.nonempty_of_card_le (le_of_lt hc)).some
     have C' := cn.some

ee05e9ce

bump to nightly-2023-03-27-22

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce86f4e05e9a9b8da5e316b22c76ce76440c56a1

0f55b099

Diff

@@ -480,7 +480,7 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
 lean 3 declaration is
   forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))
 but is expected to have type
-  forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))
+  forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))
 Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_botₓ'. -/
 theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber = 1 :=
   by
@@ -494,7 +494,7 @@ theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber
 lean 3 declaration is
   forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (Fintype.card.{u1} V _inst_1)
 but is expected to have type
-  forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (Fintype.card.{u1} V _inst_1)
+  forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (Fintype.card.{u1} V _inst_1)
 Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_topₓ'. -/
 @[simp]
 theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber = Fintype.card V :=
@@ -512,7 +512,7 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
 lean 3 declaration is
   forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))
 but is expected to have type
-  forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))
+  forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))
 Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_zero_of_infiniteₓ'. -/
 theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
     (⊤ : SimpleGraph V).chromaticNumber = 0 :=

ee05e9ce

bump to nightly-2023-03-17-00

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce7e9d53d4bbc38065db3b595cd5bd73c323bc1d

c85864d4

Diff

@@ -521,7 +521,7 @@ theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
   by_contra hc
   replace hc := pos_iff_ne_zero.mpr hc
   apply Nat.not_succ_le_self n
-  convert_to (⊤ : SimpleGraph { m | m < n + 1 }).chromaticNumber ≤ _
+  convert_to(⊤ : SimpleGraph { m | m < n + 1 }).chromaticNumber ≤ _
   · simp
   refine' (colorable_of_chromatic_number_pos hc).chromaticNumber_mono_of_embedding _
   apply embedding.complete_graph

ee05e9ce

bump to nightly-2023-03-02-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/195fcd60ff2bfe392543bceb0ec2adcdb472db4c

db7421c3

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
 
 ! This file was ported from Lean 3 source module combinatorics.simple_graph.coloring
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
+! leanprover-community/mathlib commit ee05e9ce1322178f0c12004eb93c00d2c8c00ed2
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -16,6 +16,9 @@ import Mathbin.Order.Antichain
 /-!
 # Graph Coloring
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This module defines colorings of simple graphs (also known as proper
 colorings in the literature). A graph coloring is the attribution of
 "colors" to all of its vertices such that adjacent vertices have
@@ -475,7 +478,7 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
 
 /- warning: simple_graph.chromatic_number_bot -> SimpleGraph.chromaticNumber_bot is a dubious translation:
 lean 3 declaration is
-  forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} V) (SimpleGraph.booleanAlgebra.{u1} V)))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))
+  forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))
 but is expected to have type
   forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))
 Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_botₓ'. -/
@@ -489,7 +492,7 @@ theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber
 
 /- warning: simple_graph.chromatic_number_top -> SimpleGraph.chromaticNumber_top is a dubious translation:
 lean 3 declaration is
-  forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toHasTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.booleanAlgebra.{u1} V)))) (Fintype.card.{u1} V _inst_1)
+  forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (Fintype.card.{u1} V _inst_1)
 but is expected to have type
   forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (Fintype.card.{u1} V _inst_1)
 Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_topₓ'. -/
@@ -507,7 +510,7 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
 
 /- warning: simple_graph.chromatic_number_top_eq_zero_of_infinite -> SimpleGraph.chromaticNumber_top_eq_zero_of_infinite is a dubious translation:
 lean 3 declaration is
-  forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toHasTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.booleanAlgebra.{u1} V)))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))
+  forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} V) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} V) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} V) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} V) (SimpleGraph.completeBooleanAlgebra.{u1} V))))))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))
 but is expected to have type
   forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))
 Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_zero_of_infiniteₓ'. -/

70fd9563

bump to nightly-2023-02-28-10

mathlib commit https://github.com/leanprover-community/mathlib/commit/9da1b3534b65d9661eb8f42443598a92bbb49211

533b9a85

Diff

@@ -63,19 +63,24 @@ namespace SimpleGraph
 
 variable {V : Type u} (G : SimpleGraph V)
 
+#print SimpleGraph.Coloring /-
 /-- An `α`-coloring of a simple graph `G` is a homomorphism of `G` into the complete graph on `α`.
 This is also known as a proper coloring.
 -/
 abbrev Coloring (α : Type v) :=
   G →g (⊤ : SimpleGraph α)
 #align simple_graph.coloring SimpleGraph.Coloring
+-/
 
 variable {G} {α : Type v} (C : G.Coloring α)
 
+#print SimpleGraph.Coloring.valid /-
 theorem Coloring.valid {v w : V} (h : G.Adj v w) : C v ≠ C w :=
   C.map_rel h
 #align simple_graph.coloring.valid SimpleGraph.Coloring.valid
+-/
 
+#print SimpleGraph.Coloring.mk /-
 /-- Construct a term of `simple_graph.coloring` using a function that
 assigns vertices to colors and a proof that it is as proper coloring.
 
@@ -87,46 +92,65 @@ def Coloring.mk (color : V → α) (valid : ∀ {v w : V}, G.Adj v w → color v
     G.Coloring α :=
   ⟨color, @valid⟩
 #align simple_graph.coloring.mk SimpleGraph.Coloring.mk
+-/
 
+#print SimpleGraph.Coloring.colorClass /-
 /-- The color class of a given color.
 -/
 def Coloring.colorClass (c : α) : Set V :=
   { v : V | C v = c }
 #align simple_graph.coloring.color_class SimpleGraph.Coloring.colorClass
+-/
 
+#print SimpleGraph.Coloring.colorClasses /-
 /-- The set containing all color classes. -/
 def Coloring.colorClasses : Set (Set V) :=
   (Setoid.ker C).classes
 #align simple_graph.coloring.color_classes SimpleGraph.Coloring.colorClasses
+-/
 
+#print SimpleGraph.Coloring.mem_colorClass /-
 theorem Coloring.mem_colorClass (v : V) : v ∈ C.colorClass (C v) :=
   rfl
 #align simple_graph.coloring.mem_color_class SimpleGraph.Coloring.mem_colorClass
+-/
 
+#print SimpleGraph.Coloring.colorClasses_isPartition /-
 theorem Coloring.colorClasses_isPartition : Setoid.IsPartition C.colorClasses :=
   Setoid.isPartition_classes (Setoid.ker C)
 #align simple_graph.coloring.color_classes_is_partition SimpleGraph.Coloring.colorClasses_isPartition
+-/
 
+#print SimpleGraph.Coloring.mem_colorClasses /-
 theorem Coloring.mem_colorClasses {v : V} : C.colorClass (C v) ∈ C.colorClasses :=
   ⟨v, rfl⟩
 #align simple_graph.coloring.mem_color_classes SimpleGraph.Coloring.mem_colorClasses
+-/
 
+#print SimpleGraph.Coloring.colorClasses_finite /-
 theorem Coloring.colorClasses_finite [Finite α] : C.colorClasses.Finite :=
   Setoid.finite_classes_ker _
 #align simple_graph.coloring.color_classes_finite SimpleGraph.Coloring.colorClasses_finite
+-/
 
+#print SimpleGraph.Coloring.card_colorClasses_le /-
 theorem Coloring.card_colorClasses_le [Fintype α] [Fintype C.colorClasses] :
     Fintype.card C.colorClasses ≤ Fintype.card α :=
   Setoid.card_classes_ker_le C
 #align simple_graph.coloring.card_color_classes_le SimpleGraph.Coloring.card_colorClasses_le
+-/
 
+#print SimpleGraph.Coloring.not_adj_of_mem_colorClass /-
 theorem Coloring.not_adj_of_mem_colorClass {c : α} {v w : V} (hv : v ∈ C.colorClass c)
     (hw : w ∈ C.colorClass c) : ¬G.Adj v w := fun h => C.valid h (Eq.trans hv (Eq.symm hw))
 #align simple_graph.coloring.not_adj_of_mem_color_class SimpleGraph.Coloring.not_adj_of_mem_colorClass
+-/
 
+#print SimpleGraph.Coloring.color_classes_independent /-
 theorem Coloring.color_classes_independent (c : α) : IsAntichain G.Adj (C.colorClass c) :=
   fun v hv w hw h => C.not_adj_of_mem_colorClass hv hw
 #align simple_graph.coloring.color_classes_independent SimpleGraph.Coloring.color_classes_independent
+-/
 
 -- TODO make this computable
 noncomputable instance [Fintype V] [Fintype α] : Fintype (Coloring G α) := by
@@ -137,20 +161,27 @@ noncomputable instance [Fintype V] [Fintype α] : Fintype (Coloring G α) := by
 
 variable (G)
 
+#print SimpleGraph.Colorable /-
 /-- Whether a graph can be colored by at most `n` colors. -/
 def Colorable (n : ℕ) : Prop :=
   Nonempty (G.Coloring (Fin n))
 #align simple_graph.colorable SimpleGraph.Colorable
+-/
 
+#print SimpleGraph.coloringOfIsEmpty /-
 /-- The coloring of an empty graph. -/
 def coloringOfIsEmpty [IsEmpty V] : G.Coloring α :=
   Coloring.mk isEmptyElim fun v => isEmptyElim
 #align simple_graph.coloring_of_is_empty SimpleGraph.coloringOfIsEmpty
+-/
 
+#print SimpleGraph.colorable_of_isEmpty /-
 theorem colorable_of_isEmpty [IsEmpty V] (n : ℕ) : G.Colorable n :=
   ⟨G.coloringOfIsEmpty⟩
 #align simple_graph.colorable_of_is_empty SimpleGraph.colorable_of_isEmpty
+-/
 
+#print SimpleGraph.isEmpty_of_colorable_zero /-
 theorem isEmpty_of_colorable_zero (h : G.Colorable 0) : IsEmpty V :=
   by
   constructor
@@ -158,18 +189,24 @@ theorem isEmpty_of_colorable_zero (h : G.Colorable 0) : IsEmpty V :=
   obtain ⟨i, hi⟩ := h.some v
   exact Nat.not_lt_zero _ hi
 #align simple_graph.is_empty_of_colorable_zero SimpleGraph.isEmpty_of_colorable_zero
+-/
 
+#print SimpleGraph.selfColoring /-
 /-- The "tautological" coloring of a graph, using the vertices of the graph as colors. -/
 def selfColoring : G.Coloring V :=
   Coloring.mk id fun v w => G.ne_of_adj
 #align simple_graph.self_coloring SimpleGraph.selfColoring
+-/
 
+#print SimpleGraph.chromaticNumber /-
 /-- The chromatic number of a graph is the minimal number of colors needed to color it.
 If `G` isn't colorable with finitely many colors, this will be 0. -/
 noncomputable def chromaticNumber : ℕ :=
   infₛ { n : ℕ | G.Colorable n }
 #align simple_graph.chromatic_number SimpleGraph.chromaticNumber
+-/
 
+#print SimpleGraph.recolorOfEmbedding /-
 /-- Given an embedding, there is an induced embedding of colorings. -/
 def recolorOfEmbedding {α β : Type _} (f : α ↪ β) : G.Coloring α ↪ G.Coloring β
     where
@@ -185,7 +222,9 @@ def recolorOfEmbedding {α β : Type _} (f : α ↪ β) : G.Coloring α ↪ G.Co
     rw [h]
     rfl
 #align simple_graph.recolor_of_embedding SimpleGraph.recolorOfEmbedding
+-/
 
+#print SimpleGraph.recolorOfEquiv /-
 /-- Given an equivalence, there is an induced equivalence between colorings. -/
 def recolorOfEquiv {α β : Type _} (f : α ≃ β) : G.Coloring α ≃ G.Coloring β
     where
@@ -198,28 +237,38 @@ def recolorOfEquiv {α β : Type _} (f : α ≃ β) : G.Coloring α ≃ G.Colori
     ext v
     apply Equiv.apply_symm_apply
 #align simple_graph.recolor_of_equiv SimpleGraph.recolorOfEquiv
+-/
 
+#print SimpleGraph.recolorOfCardLE /-
 /-- There is a noncomputable embedding of `α`-colorings to `β`-colorings if
 `β` has at least as large a cardinality as `α`. -/
-noncomputable def recolorOfCardLe {α β : Type _} [Fintype α] [Fintype β]
+noncomputable def recolorOfCardLE {α β : Type _} [Fintype α] [Fintype β]
     (hn : Fintype.card α ≤ Fintype.card β) : G.Coloring α ↪ G.Coloring β :=
   G.recolorOfEmbedding <| (Function.Embedding.nonempty_of_card_le hn).some
-#align simple_graph.recolor_of_card_le SimpleGraph.recolorOfCardLe
+#align simple_graph.recolor_of_card_le SimpleGraph.recolorOfCardLE
+-/
 
 variable {G}
 
+#print SimpleGraph.Colorable.mono /-
 theorem Colorable.mono {n m : ℕ} (h : n ≤ m) (hc : G.Colorable n) : G.Colorable m :=
-  ⟨G.recolorOfCardLe (by simp [h]) hc.some⟩
+  ⟨G.recolorOfCardLE (by simp [h]) hc.some⟩
 #align simple_graph.colorable.mono SimpleGraph.Colorable.mono
+-/
 
+#print SimpleGraph.Coloring.to_colorable /-
 theorem Coloring.to_colorable [Fintype α] (C : G.Coloring α) : G.Colorable (Fintype.card α) :=
-  ⟨G.recolorOfCardLe (by simp) C⟩
+  ⟨G.recolorOfCardLE (by simp) C⟩
 #align simple_graph.coloring.to_colorable SimpleGraph.Coloring.to_colorable
+-/
 
+#print SimpleGraph.colorable_of_fintype /-
 theorem colorable_of_fintype (G : SimpleGraph V) [Fintype V] : G.Colorable (Fintype.card V) :=
   G.selfColoring.to_colorable
 #align simple_graph.colorable_of_fintype SimpleGraph.colorable_of_fintype
+-/
 
+#print SimpleGraph.Colorable.toColoring /-
 /-- Noncomputably get a coloring from colorability. -/
 noncomputable def Colorable.toColoring [Fintype α] {n : ℕ} (hc : G.Colorable n)
     (hn : n ≤ Fintype.card α) : G.Coloring α :=
@@ -227,12 +276,20 @@ noncomputable def Colorable.toColoring [Fintype α] {n : ℕ} (hc : G.Colorable
   rw [← Fintype.card_fin n] at hn
   exact G.recolor_of_card_le hn hc.some
 #align simple_graph.colorable.to_coloring SimpleGraph.Colorable.toColoring
+-/
 
+/- warning: simple_graph.colorable.of_embedding -> SimpleGraph.Colorable.of_embedding is a dubious translation:
+lean 3 declaration is
+  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {V' : Type.{u2}} {G' : SimpleGraph.{u2} V'}, (SimpleGraph.Embedding.{u1, u2} V V' G G') -> (forall {n : Nat}, (SimpleGraph.Colorable.{u2} V' G' n) -> (SimpleGraph.Colorable.{u1} V G n))
+but is expected to have type
+  forall {V : Type.{u2}} {G : SimpleGraph.{u2} V} {V' : Type.{u1}} {G' : SimpleGraph.{u1} V'}, (SimpleGraph.Embedding.{u2, u1} V V' G G') -> (forall {n : Nat}, (SimpleGraph.Colorable.{u1} V' G' n) -> (SimpleGraph.Colorable.{u2} V G n))
+Case conversion may be inaccurate. Consider using '#align simple_graph.colorable.of_embedding SimpleGraph.Colorable.of_embeddingₓ'. -/
 theorem Colorable.of_embedding {V' : Type _} {G' : SimpleGraph V'} (f : G ↪g G') {n : ℕ}
     (h : G'.Colorable n) : G.Colorable n :=
   ⟨(h.toColoring (by simp)).comp f⟩
 #align simple_graph.colorable.of_embedding SimpleGraph.Colorable.of_embedding
 
+#print SimpleGraph.colorable_iff_exists_bdd_nat_coloring /-
 theorem colorable_iff_exists_bdd_nat_coloring (n : ℕ) :
     G.Colorable n ↔ ∃ C : G.Coloring ℕ, ∀ v, C v < n :=
   by
@@ -251,16 +308,22 @@ theorem colorable_iff_exists_bdd_nat_coloring (n : ℕ) :
       simp only [Fin.mk_eq_mk, Ne.def]
       exact C.valid hvw
 #align simple_graph.colorable_iff_exists_bdd_nat_coloring SimpleGraph.colorable_iff_exists_bdd_nat_coloring
+-/
 
+#print SimpleGraph.colorable_set_nonempty_of_colorable /-
 theorem colorable_set_nonempty_of_colorable {n : ℕ} (hc : G.Colorable n) :
     { n : ℕ | G.Colorable n }.Nonempty :=
   ⟨n, hc⟩
 #align simple_graph.colorable_set_nonempty_of_colorable SimpleGraph.colorable_set_nonempty_of_colorable
+-/
 
-theorem chromatic_number_bddBelow : BddBelow { n : ℕ | G.Colorable n } :=
+#print SimpleGraph.chromaticNumber_bddBelow /-
+theorem chromaticNumber_bddBelow : BddBelow { n : ℕ | G.Colorable n } :=
   ⟨0, fun _ _ => zero_le _⟩
-#align simple_graph.chromatic_number_bdd_below SimpleGraph.chromatic_number_bddBelow
+#align simple_graph.chromatic_number_bdd_below SimpleGraph.chromaticNumber_bddBelow
+-/
 
+#print SimpleGraph.chromaticNumber_le_of_colorable /-
 theorem chromaticNumber_le_of_colorable {n : ℕ} (hc : G.Colorable n) : G.chromaticNumber ≤ n :=
   by
   rw [chromatic_number]
@@ -268,12 +331,16 @@ theorem chromaticNumber_le_of_colorable {n : ℕ} (hc : G.Colorable n) : G.chrom
   fconstructor
   exact Classical.choice hc
 #align simple_graph.chromatic_number_le_of_colorable SimpleGraph.chromaticNumber_le_of_colorable
+-/
 
+#print SimpleGraph.chromaticNumber_le_card /-
 theorem chromaticNumber_le_card [Fintype α] (C : G.Coloring α) :
     G.chromaticNumber ≤ Fintype.card α :=
-  cinfₛ_le chromatic_number_bddBelow C.to_colorable
+  cinfₛ_le chromaticNumber_bddBelow C.to_colorable
 #align simple_graph.chromatic_number_le_card SimpleGraph.chromaticNumber_le_card
+-/
 
+#print SimpleGraph.colorable_chromaticNumber /-
 theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) : G.Colorable G.chromaticNumber :=
   by
   dsimp only [chromatic_number]
@@ -281,13 +348,17 @@ theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) : G.Colorable G
   apply Nat.find_spec
   exact colorable_set_nonempty_of_colorable hc
 #align simple_graph.colorable_chromatic_number SimpleGraph.colorable_chromaticNumber
+-/
 
+#print SimpleGraph.colorable_chromaticNumber_of_fintype /-
 theorem colorable_chromaticNumber_of_fintype (G : SimpleGraph V) [Finite V] :
     G.Colorable G.chromaticNumber := by
   cases nonempty_fintype V
   exact colorable_chromatic_number G.colorable_of_fintype
 #align simple_graph.colorable_chromatic_number_of_fintype SimpleGraph.colorable_chromaticNumber_of_fintype
+-/
 
+#print SimpleGraph.chromaticNumber_le_one_of_subsingleton /-
 theorem chromaticNumber_le_one_of_subsingleton (G : SimpleGraph V) [Subsingleton V] :
     G.chromaticNumber ≤ 1 := by
   rw [chromatic_number]
@@ -298,14 +369,18 @@ theorem chromaticNumber_le_one_of_subsingleton (G : SimpleGraph V) [Subsingleton
   rw [Subsingleton.elim v w]
   simp
 #align simple_graph.chromatic_number_le_one_of_subsingleton SimpleGraph.chromaticNumber_le_one_of_subsingleton
+-/
 
+#print SimpleGraph.chromaticNumber_eq_zero_of_isempty /-
 theorem chromaticNumber_eq_zero_of_isempty (G : SimpleGraph V) [IsEmpty V] :
     G.chromaticNumber = 0 := by
   rw [← nonpos_iff_eq_zero]
   apply cinfₛ_le chromatic_number_bdd_below
   apply colorable_of_is_empty
 #align simple_graph.chromatic_number_eq_zero_of_isempty SimpleGraph.chromaticNumber_eq_zero_of_isempty
+-/
 
+#print SimpleGraph.isEmpty_of_chromaticNumber_eq_zero /-
 theorem isEmpty_of_chromaticNumber_eq_zero (G : SimpleGraph V) [Finite V]
     (h : G.chromaticNumber = 0) : IsEmpty V :=
   by
@@ -313,7 +388,9 @@ theorem isEmpty_of_chromaticNumber_eq_zero (G : SimpleGraph V) [Finite V]
   rw [h] at h'
   exact G.is_empty_of_colorable_zero h'
 #align simple_graph.is_empty_of_chromatic_number_eq_zero SimpleGraph.isEmpty_of_chromaticNumber_eq_zero
+-/
 
+#print SimpleGraph.chromaticNumber_pos /-
 theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.chromaticNumber :=
   by
   apply le_cinfₛ (colorable_set_nonempty_of_colorable hc)
@@ -324,19 +401,30 @@ theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.
   obtain ⟨i, hi⟩ := hm.some (Classical.arbitrary V)
   exact Nat.not_lt_zero _ hi
 #align simple_graph.chromatic_number_pos SimpleGraph.chromaticNumber_pos
+-/
 
+#print SimpleGraph.colorable_of_chromaticNumber_pos /-
 theorem colorable_of_chromaticNumber_pos (h : 0 < G.chromaticNumber) :
     G.Colorable G.chromaticNumber :=
   by
   obtain ⟨h, hn⟩ := Nat.nonempty_of_pos_infₛ h
   exact colorable_chromatic_number hn
 #align simple_graph.colorable_of_chromatic_number_pos SimpleGraph.colorable_of_chromaticNumber_pos
+-/
 
+#print SimpleGraph.Colorable.mono_left /-
 theorem Colorable.mono_left {G' : SimpleGraph V} (h : G ≤ G') {n : ℕ} (hc : G'.Colorable n) :
     G.Colorable n :=
   ⟨hc.some.comp (Hom.mapSpanningSubgraphs h)⟩
 #align simple_graph.colorable.mono_left SimpleGraph.Colorable.mono_left
+-/
 
+/- warning: simple_graph.colorable.chromatic_number_le_of_forall_imp -> SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp is a dubious translation:
+lean 3 declaration is
+  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {V' : Type.{u2}} {G' : SimpleGraph.{u2} V'} {m : Nat}, (SimpleGraph.Colorable.{u2} V' G' m) -> (forall (n : Nat), (SimpleGraph.Colorable.{u2} V' G' n) -> (SimpleGraph.Colorable.{u1} V G n)) -> (LE.le.{0} Nat Nat.hasLe (SimpleGraph.chromaticNumber.{u1} V G) (SimpleGraph.chromaticNumber.{u2} V' G'))
+but is expected to have type
+  forall {V : Type.{u2}} {G : SimpleGraph.{u2} V} {V' : Type.{u1}} {G' : SimpleGraph.{u1} V'} {m : Nat}, (SimpleGraph.Colorable.{u1} V' G' m) -> (forall (n : Nat), (SimpleGraph.Colorable.{u1} V' G' n) -> (SimpleGraph.Colorable.{u2} V G n)) -> (LE.le.{0} Nat instLENat (SimpleGraph.chromaticNumber.{u2} V G) (SimpleGraph.chromaticNumber.{u1} V' G'))
+Case conversion may be inaccurate. Consider using '#align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.Colorable.chromaticNumber_le_of_forall_impₓ'. -/
 theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGraph V'} {m : ℕ}
     (hc : G'.Colorable m) (h : ∀ n, G'.Colorable n → G.Colorable n) :
     G.chromaticNumber ≤ G'.chromaticNumber :=
@@ -346,16 +434,25 @@ theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGra
   apply colorable_chromatic_number hc
 #align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp
 
+#print SimpleGraph.Colorable.chromaticNumber_mono /-
 theorem Colorable.chromaticNumber_mono (G' : SimpleGraph V) {m : ℕ} (hc : G'.Colorable m)
     (h : G ≤ G') : G.chromaticNumber ≤ G'.chromaticNumber :=
   hc.chromaticNumber_le_of_forall_imp fun n => Colorable.mono_left h
 #align simple_graph.colorable.chromatic_number_mono SimpleGraph.Colorable.chromaticNumber_mono
+-/
 
+/- warning: simple_graph.colorable.chromatic_number_mono_of_embedding -> SimpleGraph.Colorable.chromaticNumber_mono_of_embedding is a dubious translation:
+lean 3 declaration is
+  forall {V : Type.{u1}} {G : SimpleGraph.{u1} V} {V' : Type.{u2}} {G' : SimpleGraph.{u2} V'} {n : Nat}, (SimpleGraph.Colorable.{u2} V' G' n) -> (SimpleGraph.Embedding.{u1, u2} V V' G G') -> (LE.le.{0} Nat Nat.hasLe (SimpleGraph.chromaticNumber.{u1} V G) (SimpleGraph.chromaticNumber.{u2} V' G'))
+but is expected to have type
+  forall {V : Type.{u2}} {G : SimpleGraph.{u2} V} {V' : Type.{u1}} {G' : SimpleGraph.{u1} V'} {n : Nat}, (SimpleGraph.Colorable.{u1} V' G' n) -> (SimpleGraph.Embedding.{u2, u1} V V' G G') -> (LE.le.{0} Nat instLENat (SimpleGraph.chromaticNumber.{u2} V G) (SimpleGraph.chromaticNumber.{u1} V' G'))
+Case conversion may be inaccurate. Consider using '#align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.Colorable.chromaticNumber_mono_of_embeddingₓ'. -/
 theorem Colorable.chromaticNumber_mono_of_embedding {V' : Type _} {G' : SimpleGraph V'} {n : ℕ}
     (h : G'.Colorable n) (f : G ↪g G') : G.chromaticNumber ≤ G'.chromaticNumber :=
   h.chromaticNumber_le_of_forall_imp fun _ => Colorable.of_embedding f
 #align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.Colorable.chromaticNumber_mono_of_embedding
 
+#print SimpleGraph.chromaticNumber_eq_card_of_forall_surj /-
 theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
     (h : ∀ C' : G.Coloring α, Function.Surjective C') : G.chromaticNumber = Fintype.card α :=
   by
@@ -374,7 +471,14 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
     have h2 := Fintype.card_le_of_surjective _ h1
     exact Nat.lt_le_antisymm hc h2
 #align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_of_forall_surj
+-/
 
+/- warning: simple_graph.chromatic_number_bot -> SimpleGraph.chromaticNumber_bot is a dubious translation:
+lean 3 declaration is
+  forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} V) (SimpleGraph.booleanAlgebra.{u1} V)))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))
+but is expected to have type
+  forall {V : Type.{u1}} [_inst_1 : Nonempty.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Bot.bot.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))
+Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_botₓ'. -/
 theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber = 1 :=
   by
   let C : (⊥ : SimpleGraph V).Coloring (Fin 1) := coloring.mk (fun _ => 0) fun v w h => False.elim h
@@ -383,6 +487,12 @@ theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber
   · exact chromatic_number_pos C.to_colorable
 #align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_bot
 
+/- warning: simple_graph.chromatic_number_top -> SimpleGraph.chromaticNumber_top is a dubious translation:
+lean 3 declaration is
+  forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toHasTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.booleanAlgebra.{u1} V)))) (Fintype.card.{u1} V _inst_1)
+but is expected to have type
+  forall {V : Type.{u1}} [_inst_1 : Fintype.{u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (Fintype.card.{u1} V _inst_1)
+Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_topₓ'. -/
 @[simp]
 theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber = Fintype.card V :=
   by
@@ -395,6 +505,12 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
   exact C.valid h
 #align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_top
 
+/- warning: simple_graph.chromatic_number_top_eq_zero_of_infinite -> SimpleGraph.chromaticNumber_top_eq_zero_of_infinite is a dubious translation:
+lean 3 declaration is
+  forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toHasTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.booleanAlgebra.{u1} V)))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))
+but is expected to have type
+  forall (V : Type.{u1}) [_inst_1 : Infinite.{succ u1} V], Eq.{1} Nat (SimpleGraph.chromaticNumber.{u1} V (Top.top.{u1} (SimpleGraph.{u1} V) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} V) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} V)))) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))
+Case conversion may be inaccurate. Consider using '#align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_zero_of_infiniteₓ'. -/
 theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
     (⊤ : SimpleGraph V).chromaticNumber = 0 :=
   by
@@ -409,6 +525,7 @@ theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
   exact (Function.Embedding.subtype _).trans (Infinite.natEmbedding V)
 #align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_zero_of_infinite
 
+#print SimpleGraph.CompleteBipartiteGraph.bicoloring /-
 /-- The bicoloring of a complete bipartite graph using whether a vertex
 is on the left or on the right. -/
 def CompleteBipartiteGraph.bicoloring (V W : Type _) : (completeBipartiteGraph V W).Coloring Bool :=
@@ -417,7 +534,14 @@ def CompleteBipartiteGraph.bicoloring (V W : Type _) : (completeBipartiteGraph V
       intro v w
       cases v <;> cases w <;> simp)
 #align simple_graph.complete_bipartite_graph.bicoloring SimpleGraph.CompleteBipartiteGraph.bicoloring
+-/
 
+/- warning: simple_graph.complete_bipartite_graph.chromatic_number -> SimpleGraph.CompleteBipartiteGraph.chromaticNumber is a dubious translation:
+lean 3 declaration is
+  forall {V : Type.{u1}} {W : Type.{u2}} [_inst_1 : Nonempty.{succ u1} V] [_inst_2 : Nonempty.{succ u2} W], Eq.{1} Nat (SimpleGraph.chromaticNumber.{max u1 u2} (Sum.{u1, u2} V W) (completeBipartiteGraph.{u1, u2} V W)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne))))
+but is expected to have type
+  forall {V : Type.{u2}} {W : Type.{u1}} [_inst_1 : Nonempty.{succ u2} V] [_inst_2 : Nonempty.{succ u1} W], Eq.{1} Nat (SimpleGraph.chromaticNumber.{max u2 u1} (Sum.{u2, u1} V W) (completeBipartiteGraph.{u2, u1} V W)) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2))
+Case conversion may be inaccurate. Consider using '#align simple_graph.complete_bipartite_graph.chromatic_number SimpleGraph.CompleteBipartiteGraph.chromaticNumberₓ'. -/
 theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [Nonempty W] :
     (completeBipartiteGraph V W).chromaticNumber = 2 :=
   by
@@ -440,6 +564,7 @@ theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [None
 /-! ### Cliques -/
 
 
+#print SimpleGraph.IsClique.card_le_of_coloring /-
 theorem IsClique.card_le_of_coloring {s : Finset V} (h : G.IsClique s) [Fintype α]
     (C : G.Coloring α) : s.card ≤ Fintype.card α :=
   by
@@ -449,14 +574,18 @@ theorem IsClique.card_le_of_coloring {s : Finset V} (h : G.IsClique s) [Fintype
   convert Fintype.card_le_of_injective _ (C.comp f.to_hom).injective_of_top_hom using 1
   simp
 #align simple_graph.is_clique.card_le_of_coloring SimpleGraph.IsClique.card_le_of_coloring
+-/
 
+#print SimpleGraph.IsClique.card_le_of_colorable /-
 theorem IsClique.card_le_of_colorable {s : Finset V} (h : G.IsClique s) {n : ℕ}
     (hc : G.Colorable n) : s.card ≤ n :=
   by
   convert h.card_le_of_coloring hc.some
   simp
 #align simple_graph.is_clique.card_le_of_colorable SimpleGraph.IsClique.card_le_of_colorable
+-/
 
+#print SimpleGraph.IsClique.card_le_chromaticNumber /-
 -- TODO eliminate `finite V` constraint once chromatic numbers are refactored.
 -- This is just to ensure the chromatic number exists.
 theorem IsClique.card_le_chromaticNumber [Finite V] {s : Finset V} (h : G.IsClique s) :
@@ -464,7 +593,9 @@ theorem IsClique.card_le_chromaticNumber [Finite V] {s : Finset V} (h : G.IsCliq
   cases nonempty_fintype V
   exact h.card_le_of_colorable G.colorable_chromatic_number_of_fintype
 #align simple_graph.is_clique.card_le_chromatic_number SimpleGraph.IsClique.card_le_chromaticNumber
+-/
 
+#print SimpleGraph.Colorable.cliqueFree /-
 protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n < m) :
     G.CliqueFree m := by
   by_contra h
@@ -472,13 +603,16 @@ protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n
   obtain ⟨s, h, rfl⟩ := h
   exact Nat.lt_le_antisymm hm (h.card_le_of_colorable hc)
 #align simple_graph.colorable.clique_free SimpleGraph.Colorable.cliqueFree
+-/
 
+#print SimpleGraph.cliqueFree_of_chromaticNumber_lt /-
 -- TODO eliminate `finite V` constraint once chromatic numbers are refactored.
 -- This is just to ensure the chromatic number exists.
 theorem cliqueFree_of_chromaticNumber_lt [Finite V] {n : ℕ} (hc : G.chromaticNumber < n) :
     G.CliqueFree n :=
   G.colorable_chromaticNumber_of_fintype.CliqueFree hc
 #align simple_graph.clique_free_of_chromatic_number_lt SimpleGraph.cliqueFree_of_chromaticNumber_lt
+-/
 
 end SimpleGraph

70fd9563

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

70fd9563

chore: minor backports from nightly-testing (#12531)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

c81020ba

Diff

@@ -307,8 +307,8 @@ theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) :
     G.Colorable (ENat.toNat G.chromaticNumber) := by
   classical
   rw [hc.chromaticNumber_eq_sInf, Nat.sInf_def]
-  apply Nat.find_spec
-  exact colorable_set_nonempty_of_colorable hc
+  · apply Nat.find_spec
+  · exact colorable_set_nonempty_of_colorable hc
 #align simple_graph.colorable_chromatic_number SimpleGraph.colorable_chromaticNumber
 
 theorem colorable_chromaticNumber_of_fintype (G : SimpleGraph V) [Finite V] :

70fd9563

chore: backports from #11997, adaptations for nightly-2024-04-07 (#12176)

These are changes from #11997, the latest adaptation PR for nightly-2024-04-07, which can be made directly on master.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>

02293f49

Diff

@@ -432,7 +432,7 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
 theorem chromaticNumber_top_eq_top_of_infinite (V : Type*) [Infinite V] :
     (⊤ : SimpleGraph V).chromaticNumber = ⊤ := by
   by_contra hc
-  rw [← Ne.def, chromaticNumber_ne_top_iff_exists] at hc
+  rw [← Ne, chromaticNumber_ne_top_iff_exists] at hc
   obtain ⟨n, ⟨hn⟩⟩ := hc
   exact not_injective_infinite_finite _ hn.injective_of_top_hom
 #align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_top_of_infinite

70fd9563

chore: avoid Ne.def (adaptation for nightly-2024-03-27) (#11801)

1b40c7bc

Diff

@@ -260,7 +260,7 @@ theorem colorable_iff_exists_bdd_nat_coloring (n : ℕ) :
     refine' ⟨Coloring.mk _ _⟩
     · exact fun v => ⟨C v, Cf v⟩
     · rintro v w hvw
-      simp only [Fin.mk_eq_mk, Ne.def]
+      simp only [Fin.mk_eq_mk, Ne]
       exact C.valid hvw
 #align simple_graph.colorable_iff_exists_bdd_nat_coloring SimpleGraph.colorable_iff_exists_bdd_nat_coloring

70fd9563

feat(SimpleGraph/Coloring): Surjectivity of graph colorings (#11397)

Add two simple results on graph colorings with χ(G) colors.

If r ≤ χ(G) and C is an r-coloring of G then C is surjective
If G has an α-coloring then χ(G) = |α| iff every such coloring is surjective.

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

1111ecb4

Diff

@@ -56,20 +56,20 @@ a complete graph, whose vertices represent the colors.
   * develop API for partial colorings, likely as colorings of subgraphs (`H.coe.Coloring α`)
 -/
 
+open Fintype Function
 
 universe u v
 
 namespace SimpleGraph
 
-variable {V : Type u} (G : SimpleGraph V)
-
+variable {V : Type u} (G : SimpleGraph V) {n : ℕ}
 /-- An `α`-coloring of a simple graph `G` is a homomorphism of `G` into the complete graph on `α`.
 This is also known as a proper coloring.
 -/
 abbrev Coloring (α : Type v) := G →g (⊤ : SimpleGraph α)
 #align simple_graph.coloring SimpleGraph.Coloring
 
-variable {G} {α : Type v} (C : G.Coloring α)
+variable {G} {α β : Type*} (C : G.Coloring α)
 
 theorem Coloring.valid {v w : V} (h : G.Adj v w) : C v ≠ C w :=
   C.map_rel h
@@ -191,6 +191,9 @@ def recolorOfEmbedding {α β : Type*} (f : α ↪ β) : G.Coloring α ↪ G.Col
     rfl
 #align simple_graph.recolor_of_embedding SimpleGraph.recolorOfEmbedding
 
+@[simp] lemma coe_recolorOfEmbedding (f : α ↪ β) :
+    ⇑(G.recolorOfEmbedding f) = (Embedding.completeGraph f).toHom.comp := rfl
+
 /-- Given an equivalence, there is an induced equivalence between colorings. -/
 def recolorOfEquiv {α β : Type*} (f : α ≃ β) : G.Coloring α ≃ G.Coloring β where
   toFun := G.recolorOfEmbedding f.toEmbedding
@@ -203,6 +206,9 @@ def recolorOfEquiv {α β : Type*} (f : α ≃ β) : G.Coloring α ≃ G.Colorin
     apply Equiv.apply_symm_apply
 #align simple_graph.recolor_of_equiv SimpleGraph.recolorOfEquiv
 
+@[simp] lemma coe_recolorOfEquiv (f : α ≃ β) :
+    ⇑(G.recolorOfEquiv f) = (Embedding.completeGraph f).toHom.comp := rfl
+
 /-- There is a noncomputable embedding of `α`-colorings to `β`-colorings if
 `β` has at least as large a cardinality as `α`. -/
 noncomputable def recolorOfCardLE {α β : Type*} [Fintype α] [Fintype β]
@@ -210,6 +216,10 @@ noncomputable def recolorOfCardLE {α β : Type*} [Fintype α] [Fintype β]
   G.recolorOfEmbedding <| (Function.Embedding.nonempty_of_card_le hn).some
 #align simple_graph.recolor_of_card_le SimpleGraph.recolorOfCardLE
 
+@[simp] lemma coe_recolorOfCardLE [Fintype α] [Fintype β] (hαβ : card α ≤ card β) :
+    ⇑(G.recolorOfCardLE hαβ) =
+      (Embedding.completeGraph (Embedding.nonempty_of_card_le hαβ).some).toHom.comp := rfl
+
 variable {G}
 
 theorem Colorable.mono {n m : ℕ} (h : n ≤ m) (hc : G.Colorable n) : G.Colorable m :=
@@ -287,11 +297,10 @@ theorem chromaticNumber_le_iff_colorable {n : ℕ} : G.chromaticNumber ≤ n ↔
   rw [Set.mem_setOf_eq] at this
   exact this.mono h
 
+-- 2024-03-21
+@[deprecated Colorable.chromaticNumber_le]
 theorem chromaticNumber_le_card [Fintype α] (C : G.Coloring α) :
-    G.chromaticNumber ≤ Fintype.card α := by
-  rw [C.colorable.chromaticNumber_eq_sInf]
-  norm_cast
-  exact csInf_le chromaticNumber_bddBelow C.colorable
+    G.chromaticNumber ≤ Fintype.card α := C.colorable.chromaticNumber_le
 #align simple_graph.chromatic_number_le_card SimpleGraph.chromaticNumber_le_card
 
 theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) :
@@ -374,36 +383,44 @@ theorem chromaticNumber_mono_of_embedding {V' : Type*} {G' : SimpleGraph V'}
   chromaticNumber_le_of_forall_imp fun _ => Colorable.of_embedding f
 #align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.chromaticNumber_mono_of_embedding
 
-theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
-    (h : ∀ C' : G.Coloring α, Function.Surjective C') : G.chromaticNumber = Fintype.card α := by
-  apply le_antisymm
-  · apply chromaticNumber_le_card C
-  · rw [C.colorable.chromaticNumber_eq_sInf, Nat.cast_le]
-    by_contra hc
-    rw [not_le] at hc
-    obtain ⟨n, cn, hc⟩ :=
-      exists_lt_of_csInf_lt (colorable_set_nonempty_of_colorable C.colorable) hc
-    rw [← Fintype.card_fin n] at hc
-    have f := (Function.Embedding.nonempty_of_card_le (le_of_lt hc)).some
-    have C' := cn.some
-    specialize h (G.recolorOfEmbedding f C')
-    have h1 : Function.Surjective f := Function.Surjective.of_comp h
-    have h2 := Fintype.card_le_of_surjective _ h1
-    exact Nat.lt_le_asymm hc h2
-#align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_of_forall_surj
+lemma card_le_chromaticNumber_iff_forall_surjective [Fintype α] :
+    card α ≤ G.chromaticNumber ↔ ∀ C : G.Coloring α, Surjective C := by
+  refine ⟨fun h C ↦ ?_, fun h ↦ ?_⟩
+  · rw [C.colorable.chromaticNumber_eq_sInf, Nat.cast_le] at h
+    intro i
+    by_contra! hi
+    let D : G.Coloring {a // a ≠ i} := ⟨fun v ↦ ⟨C v, hi v⟩, (C.valid · <| congr_arg Subtype.val ·)⟩
+    classical
+    exact Nat.not_mem_of_lt_sInf ((Nat.pred_lt' <| card_pos_iff.2 ⟨i⟩).trans_le h)
+      ⟨G.recolorOfEquiv (equivOfCardEq <| by simp [Nat.pred_eq_sub_one]) D⟩
+  · simp only [chromaticNumber, Set.mem_setOf_eq, le_iInf_iff, Nat.cast_le, exists_prop]
+    rintro i ⟨C⟩
+    contrapose! h
+    refine ⟨G.recolorOfCardLE (by simpa using h.le) C, fun hC ↦ ?_⟩
+    dsimp at hC
+    simpa [h.not_le] using Fintype.card_le_of_surjective _ hC.of_comp
+
+lemma le_chromaticNumber_iff_forall_surjective :
+    n ≤ G.chromaticNumber ↔ ∀ C : G.Coloring (Fin n), Surjective C := by
+  simp [← card_le_chromaticNumber_iff_forall_surjective]
+
+lemma chromaticNumber_eq_card_iff_forall_surjective [Fintype α] (hG : G.Colorable (card α)) :
+    G.chromaticNumber = card α ↔ ∀ C : G.Coloring α, Surjective C := by
+  rw [← hG.chromaticNumber_le.ge_iff_eq, card_le_chromaticNumber_iff_forall_surjective]
+#align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_iff_forall_surjective
+
+lemma chromaticNumber_eq_iff_forall_surjective (hG : G.Colorable n) :
+    G.chromaticNumber = n ↔ ∀ C : G.Coloring (Fin n), Surjective C := by
+  rw [← hG.chromaticNumber_le.ge_iff_eq, le_chromaticNumber_iff_forall_surjective]
 
 theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber = 1 := by
-  let C : (⊥ : SimpleGraph V).Coloring (Fin 1) :=
-      Coloring.mk (fun _ => 0) fun {v w} h => False.elim h
-  apply le_antisymm
-  · exact chromaticNumber_le_card C
-  · rw [ENat.one_le_iff_pos]
-    exact chromaticNumber_pos C.colorable
+  have : (⊥ : SimpleGraph V).Colorable 1 := ⟨.mk 0 $ by simp⟩
+  exact this.chromaticNumber_le.antisymm $ ENat.one_le_iff_pos.2 $ chromaticNumber_pos this
 #align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_bot
 
 @[simp]
 theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber = Fintype.card V := by
-  apply chromaticNumber_eq_card_of_forall_surj (selfColoring _)
+  rw [chromaticNumber_eq_card_iff_forall_surjective (selfColoring _).colorable]
   intro C
   rw [← Finite.injective_iff_surjective]
   intro v w
@@ -431,21 +448,17 @@ def CompleteBipartiteGraph.bicoloring (V W : Type*) : (completeBipartiteGraph V
 
 theorem CompleteBipartiteGraph.chromaticNumber {V W : Type*} [Nonempty V] [Nonempty W] :
     (completeBipartiteGraph V W).chromaticNumber = 2 := by
-  apply chromaticNumber_eq_card_of_forall_surj (CompleteBipartiteGraph.bicoloring V W)
+  rw [← Nat.cast_two, chromaticNumber_eq_iff_forall_surjective
+    (by simpa using (CompleteBipartiteGraph.bicoloring V W).colorable)]
   intro C b
   have v := Classical.arbitrary V
   have w := Classical.arbitrary W
   have h : (completeBipartiteGraph V W).Adj (Sum.inl v) (Sum.inr w) := by simp
-  have hn := C.valid h
   by_cases he : C (Sum.inl v) = b
   · exact ⟨_, he⟩
-  · by_cases he' : C (Sum.inr w) = b
-    · exact ⟨_, he'⟩
-    · exfalso
-      cases b <;>
-        simp only [Bool.eq_true_eq_not_eq_false, Bool.eq_false_eq_not_eq_true] at he he' <;>
-          rw [he, he'] at hn <;>
-        contradiction
+  by_cases he' : C (Sum.inr w) = b
+  · exact ⟨_, he'⟩
+  · simpa using two_lt_card_iff.2 ⟨_, _, _, C.valid h, he, he'⟩
 #align simple_graph.complete_bipartite_graph.chromatic_number SimpleGraph.CompleteBipartiteGraph.chromaticNumber
 
 /-! ### Cliques -/

70fd9563

style: homogenise porting notes (#11145)

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

converts "--porting note" into "-- Porting note";
converts "porting note" into "Porting note".

8be0b69c

Diff

@@ -114,7 +114,7 @@ theorem Coloring.colorClasses_finite [Finite α] : C.colorClasses.Finite :=
 theorem Coloring.card_colorClasses_le [Fintype α] [Fintype C.colorClasses] :
     Fintype.card C.colorClasses ≤ Fintype.card α := by
   simp [colorClasses]
-  -- porting note: brute force instance declaration `[Fintype (Setoid.classes (Setoid.ker C))]`
+  -- Porting note: brute force instance declaration `[Fintype (Setoid.classes (Setoid.ker C))]`
   haveI : Fintype (Setoid.classes (Setoid.ker C)) := by assumption
   convert Setoid.card_classes_ker_le C
 #align simple_graph.coloring.card_color_classes_le SimpleGraph.Coloring.card_colorClasses_le

70fd9563

refactor: make SimpleGraph.chromaticNumber be ENat-valued (#8883)

This removes an awkwardness of the API, where theorems had to include colorability hypotheses. This trades that awkwardness for a smaller one, which is that one writes G.Colorable (ENat.toNat G.chromaticNumber) rather than G.Colorable G.chromaticNumber.

It would be good to have a followup refactoring PR to more carefully evaluate the API after this change.

59641348

Diff

@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
 -/
 import Mathlib.Combinatorics.SimpleGraph.Clique
+import Mathlib.Data.ENat.Lattice
 import Mathlib.Data.Nat.Lattice
 import Mathlib.Data.Setoid.Partition
 import Mathlib.Order.Antichain
@@ -30,8 +31,10 @@ a complete graph, whose vertices represent the colors.
   is whether there exists a coloring with at most *n* colors.
 
 * `G.chromaticNumber` is the minimal `n` such that `G` is
-  `n`-colorable, or `0` if it cannot be colored with finitely many
+  `n`-colorable, or `⊤` if it cannot be colored with finitely many
   colors.
+  (Cardinal-valued chromatic numbers are more niche, so we stick to `ℕ∞`.)
+  We write `G.chromaticNumber ≠ ⊤` to mean a graph is colorable with finitely many colors.
 
 * `C.colorClass c` is the set of vertices colored by `c : α` in the
   coloring `C : G.Coloring α`.
@@ -157,11 +160,24 @@ def selfColoring : G.Coloring V := Coloring.mk id fun {_ _} => G.ne_of_adj
 #align simple_graph.self_coloring SimpleGraph.selfColoring
 
 /-- The chromatic number of a graph is the minimal number of colors needed to color it.
-If `G` isn't colorable with finitely many colors, this will be 0. -/
-noncomputable def chromaticNumber : ℕ :=
-  sInf { n : ℕ | G.Colorable n }
+This is `⊤` (infinity) iff `G` isn't colorable with finitely many colors.
+
+If `G` is colorable, then `ENat.toNat G.chromaticNumber` is the `ℕ`-valued chromatic number. -/
+noncomputable def chromaticNumber : ℕ∞ := ⨅ n ∈ setOf G.Colorable, (n : ℕ∞)
 #align simple_graph.chromatic_number SimpleGraph.chromaticNumber
 
+lemma chromaticNumber_eq_biInf {G : SimpleGraph V} :
+    G.chromaticNumber = ⨅ n ∈ setOf G.Colorable, (n : ℕ∞) := rfl
+
+lemma chromaticNumber_eq_iInf {G : SimpleGraph V} :
+    G.chromaticNumber = ⨅ n : {m | G.Colorable m}, (n : ℕ∞) := by
+  rw [chromaticNumber, iInf_subtype]
+
+lemma Colorable.chromaticNumber_eq_sInf {G : SimpleGraph V} {n} (h : G.Colorable n) :
+    G.chromaticNumber = sInf {n' : ℕ | G.Colorable n'} := by
+  rw [ENat.coe_sInf, chromaticNumber]
+  exact ⟨_, h⟩
+
 /-- Given an embedding, there is an induced embedding of colorings. -/
 def recolorOfEmbedding {α β : Type*} (f : α ↪ β) : G.Coloring α ↪ G.Coloring β where
   toFun C := (Embedding.completeGraph f).toHom.comp C
@@ -200,12 +216,12 @@ theorem Colorable.mono {n m : ℕ} (h : n ≤ m) (hc : G.Colorable n) : G.Colora
   ⟨G.recolorOfCardLE (by simp [h]) hc.some⟩
 #align simple_graph.colorable.mono SimpleGraph.Colorable.mono
 
-theorem Coloring.to_colorable [Fintype α] (C : G.Coloring α) : G.Colorable (Fintype.card α) :=
+theorem Coloring.colorable [Fintype α] (C : G.Coloring α) : G.Colorable (Fintype.card α) :=
   ⟨G.recolorOfCardLE (by simp) C⟩
-#align simple_graph.coloring.to_colorable SimpleGraph.Coloring.to_colorable
+#align simple_graph.coloring.to_colorable SimpleGraph.Coloring.colorable
 
 theorem colorable_of_fintype (G : SimpleGraph V) [Fintype V] : G.Colorable (Fintype.card V) :=
-  G.selfColoring.to_colorable
+  G.selfColoring.colorable
 #align simple_graph.colorable_of_fintype SimpleGraph.colorable_of_fintype
 
 /-- Noncomputably get a coloring from colorability. -/
@@ -247,47 +263,63 @@ theorem chromaticNumber_bddBelow : BddBelow { n : ℕ | G.Colorable n } :=
   ⟨0, fun _ _ => zero_le _⟩
 #align simple_graph.chromatic_number_bdd_below SimpleGraph.chromaticNumber_bddBelow
 
-theorem chromaticNumber_le_of_colorable {n : ℕ} (hc : G.Colorable n) : G.chromaticNumber ≤ n := by
-  rw [chromaticNumber]
+theorem Colorable.chromaticNumber_le {n : ℕ} (hc : G.Colorable n) : G.chromaticNumber ≤ n := by
+  rw [hc.chromaticNumber_eq_sInf]
+  norm_cast
   apply csInf_le chromaticNumber_bddBelow
-  constructor
-  exact Classical.choice hc
-#align simple_graph.chromatic_number_le_of_colorable SimpleGraph.chromaticNumber_le_of_colorable
+  exact hc
+#align simple_graph.chromatic_number_le_of_colorable SimpleGraph.Colorable.chromaticNumber_le
+
+theorem chromaticNumber_ne_top_iff_exists : G.chromaticNumber ≠ ⊤ ↔ ∃ n, G.Colorable n := by
+  rw [chromaticNumber]
+  convert_to ⨅ n : {m | G.Colorable m}, (n : ℕ∞) ≠ ⊤ ↔ _
+  · rw [iInf_subtype]
+  rw [← lt_top_iff_ne_top, ENat.iInf_coe_lt_top]
+  simp
+
+theorem chromaticNumber_le_iff_colorable {n : ℕ} : G.chromaticNumber ≤ n ↔ G.Colorable n := by
+  refine ⟨fun h ↦ ?_, Colorable.chromaticNumber_le⟩
+  have : G.chromaticNumber ≠ ⊤ := (trans h (WithTop.coe_lt_top n)).ne
+  rw [chromaticNumber_ne_top_iff_exists] at this
+  obtain ⟨m, hm⟩ := this
+  rw [hm.chromaticNumber_eq_sInf, Nat.cast_le] at h
+  have := Nat.sInf_mem (⟨m, hm⟩ : {n' | G.Colorable n'}.Nonempty)
+  rw [Set.mem_setOf_eq] at this
+  exact this.mono h
 
 theorem chromaticNumber_le_card [Fintype α] (C : G.Coloring α) :
-    G.chromaticNumber ≤ Fintype.card α :=
-  csInf_le chromaticNumber_bddBelow C.to_colorable
+    G.chromaticNumber ≤ Fintype.card α := by
+  rw [C.colorable.chromaticNumber_eq_sInf]
+  norm_cast
+  exact csInf_le chromaticNumber_bddBelow C.colorable
 #align simple_graph.chromatic_number_le_card SimpleGraph.chromaticNumber_le_card
 
-theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) : G.Colorable G.chromaticNumber := by
+theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) :
+    G.Colorable (ENat.toNat G.chromaticNumber) := by
   classical
-  dsimp only [chromaticNumber]
-  rw [Nat.sInf_def]
+  rw [hc.chromaticNumber_eq_sInf, Nat.sInf_def]
   apply Nat.find_spec
   exact colorable_set_nonempty_of_colorable hc
 #align simple_graph.colorable_chromatic_number SimpleGraph.colorable_chromaticNumber
 
 theorem colorable_chromaticNumber_of_fintype (G : SimpleGraph V) [Finite V] :
-    G.Colorable G.chromaticNumber := by
+    G.Colorable (ENat.toNat G.chromaticNumber) := by
   cases nonempty_fintype V
   exact colorable_chromaticNumber G.colorable_of_fintype
 #align simple_graph.colorable_chromatic_number_of_fintype SimpleGraph.colorable_chromaticNumber_of_fintype
 
 theorem chromaticNumber_le_one_of_subsingleton (G : SimpleGraph V) [Subsingleton V] :
     G.chromaticNumber ≤ 1 := by
-  rw [chromaticNumber]
-  apply csInf_le chromaticNumber_bddBelow
-  constructor
-  refine' Coloring.mk (fun _ => 0) _
-  intro v w
-  rw [Subsingleton.elim v w]
+  rw [← Nat.cast_one, chromaticNumber_le_iff_colorable]
+  refine ⟨Coloring.mk (fun _ => 0) ?_⟩
+  intros v w
+  cases Subsingleton.elim v w
   simp
 #align simple_graph.chromatic_number_le_one_of_subsingleton SimpleGraph.chromaticNumber_le_one_of_subsingleton
 
 theorem chromaticNumber_eq_zero_of_isempty (G : SimpleGraph V) [IsEmpty V] :
     G.chromaticNumber = 0 := by
-  rw [← nonpos_iff_eq_zero]
-  apply csInf_le chromaticNumber_bddBelow
+  rw [← nonpos_iff_eq_zero, ← Nat.cast_zero, chromaticNumber_le_iff_colorable]
   apply colorable_of_isEmpty
 #align simple_graph.chromatic_number_eq_zero_of_isempty SimpleGraph.chromaticNumber_eq_zero_of_isempty
 
@@ -299,6 +331,7 @@ theorem isEmpty_of_chromaticNumber_eq_zero (G : SimpleGraph V) [Finite V]
 #align simple_graph.is_empty_of_chromatic_number_eq_zero SimpleGraph.isEmpty_of_chromaticNumber_eq_zero
 
 theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.chromaticNumber := by
+  rw [hc.chromaticNumber_eq_sInf, Nat.cast_pos]
   apply le_csInf (colorable_set_nonempty_of_colorable hc)
   intro m hm
   by_contra h'
@@ -308,43 +341,48 @@ theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.
   exact Nat.not_lt_zero _ h₁
 #align simple_graph.chromatic_number_pos SimpleGraph.chromaticNumber_pos
 
-theorem colorable_of_chromaticNumber_pos (h : 0 < G.chromaticNumber) :
-    G.Colorable G.chromaticNumber := by
-  obtain ⟨h, hn⟩ := Nat.nonempty_of_pos_sInf h
+theorem colorable_of_chromaticNumber_ne_top (h : G.chromaticNumber ≠ ⊤) :
+    G.Colorable (ENat.toNat G.chromaticNumber) := by
+  rw [chromaticNumber_ne_top_iff_exists] at h
+  obtain ⟨n, hn⟩ := h
   exact colorable_chromaticNumber hn
-#align simple_graph.colorable_of_chromatic_number_pos SimpleGraph.colorable_of_chromaticNumber_pos
+#align simple_graph.colorable_of_chromatic_number_pos SimpleGraph.colorable_of_chromaticNumber_ne_top
 
 theorem Colorable.mono_left {G' : SimpleGraph V} (h : G ≤ G') {n : ℕ} (hc : G'.Colorable n) :
     G.Colorable n :=
   ⟨hc.some.comp (Hom.mapSpanningSubgraphs h)⟩
 #align simple_graph.colorable.mono_left SimpleGraph.Colorable.mono_left
 
-theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type*} {G' : SimpleGraph V'} {m : ℕ}
-    (hc : G'.Colorable m) (h : ∀ n, G'.Colorable n → G.Colorable n) :
+theorem chromaticNumber_le_of_forall_imp {V' : Type*} {G' : SimpleGraph V'}
+    (h : ∀ n, G'.Colorable n → G.Colorable n) :
     G.chromaticNumber ≤ G'.chromaticNumber := by
-  apply csInf_le chromaticNumber_bddBelow
-  apply h
-  apply colorable_chromaticNumber hc
-#align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp
-
-theorem Colorable.chromaticNumber_mono (G' : SimpleGraph V) {m : ℕ} (hc : G'.Colorable m)
+  rw [chromaticNumber, chromaticNumber]
+  simp only [Set.mem_setOf_eq, le_iInf_iff]
+  intro m hc
+  have := h _ hc
+  rw [← chromaticNumber_le_iff_colorable] at this
+  exact this
+#align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.chromaticNumber_le_of_forall_imp
+
+theorem chromaticNumber_mono (G' : SimpleGraph V)
     (h : G ≤ G') : G.chromaticNumber ≤ G'.chromaticNumber :=
-  hc.chromaticNumber_le_of_forall_imp fun _ => Colorable.mono_left h
-#align simple_graph.colorable.chromatic_number_mono SimpleGraph.Colorable.chromaticNumber_mono
+  chromaticNumber_le_of_forall_imp fun _ => Colorable.mono_left h
+#align simple_graph.colorable.chromatic_number_mono SimpleGraph.chromaticNumber_mono
 
-theorem Colorable.chromaticNumber_mono_of_embedding {V' : Type*} {G' : SimpleGraph V'} {n : ℕ}
-    (h : G'.Colorable n) (f : G ↪g G') : G.chromaticNumber ≤ G'.chromaticNumber :=
-  h.chromaticNumber_le_of_forall_imp fun _ => Colorable.of_embedding f
-#align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.Colorable.chromaticNumber_mono_of_embedding
+theorem chromaticNumber_mono_of_embedding {V' : Type*} {G' : SimpleGraph V'}
+    (f : G ↪g G') : G.chromaticNumber ≤ G'.chromaticNumber :=
+  chromaticNumber_le_of_forall_imp fun _ => Colorable.of_embedding f
+#align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.chromaticNumber_mono_of_embedding
 
 theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
     (h : ∀ C' : G.Coloring α, Function.Surjective C') : G.chromaticNumber = Fintype.card α := by
   apply le_antisymm
   · apply chromaticNumber_le_card C
-  · by_contra hc
+  · rw [C.colorable.chromaticNumber_eq_sInf, Nat.cast_le]
+    by_contra hc
     rw [not_le] at hc
     obtain ⟨n, cn, hc⟩ :=
-      exists_lt_of_csInf_lt (colorable_set_nonempty_of_colorable C.to_colorable) hc
+      exists_lt_of_csInf_lt (colorable_set_nonempty_of_colorable C.colorable) hc
     rw [← Fintype.card_fin n] at hc
     have f := (Function.Embedding.nonempty_of_card_le (le_of_lt hc)).some
     have C' := cn.some
@@ -359,7 +397,8 @@ theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber
       Coloring.mk (fun _ => 0) fun {v w} h => False.elim h
   apply le_antisymm
   · exact chromaticNumber_le_card C
-  · exact chromaticNumber_pos C.to_colorable
+  · rw [ENat.one_le_iff_pos]
+    exact chromaticNumber_pos C.colorable
 #align simple_graph.chromatic_number_bot SimpleGraph.chromaticNumber_bot
 
 @[simp]
@@ -373,19 +412,13 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
   exact C.valid h
 #align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_top
 
-theorem chromaticNumber_top_eq_zero_of_infinite (V : Type*) [Infinite V] :
-    (⊤ : SimpleGraph V).chromaticNumber = 0 := by
-  let n := (⊤ : SimpleGraph V).chromaticNumber
+theorem chromaticNumber_top_eq_top_of_infinite (V : Type*) [Infinite V] :
+    (⊤ : SimpleGraph V).chromaticNumber = ⊤ := by
   by_contra hc
-  replace hc := pos_iff_ne_zero.mpr hc
-  apply Nat.not_succ_le_self n
-  convert_to (⊤ : SimpleGraph { m | m < n + 1 }).chromaticNumber ≤ _
-  · rw [SimpleGraph.chromaticNumber_top, Fintype.card_ofFinset,
-        Finset.card_range, Nat.succ_eq_add_one]
-  refine' (colorable_of_chromaticNumber_pos hc).chromaticNumber_mono_of_embedding _
-  apply Embedding.completeGraph
-  exact (Function.Embedding.subtype _).trans (Infinite.natEmbedding V)
-#align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_zero_of_infinite
+  rw [← Ne.def, chromaticNumber_ne_top_iff_exists] at hc
+  obtain ⟨n, ⟨hn⟩⟩ := hc
+  exact not_injective_infinite_finite _ hn.injective_of_top_hom
+#align simple_graph.chromatic_number_top_eq_zero_of_infinite SimpleGraph.chromaticNumber_top_eq_top_of_infinite
 
 /-- The bicoloring of a complete bipartite graph using whether a vertex
 is on the left or on the right. -/
@@ -433,12 +466,17 @@ theorem IsClique.card_le_of_colorable {s : Finset V} (h : G.IsClique s) {n : ℕ
   simp
 #align simple_graph.is_clique.card_le_of_colorable SimpleGraph.IsClique.card_le_of_colorable
 
--- TODO eliminate `Finite V` constraint once chromatic numbers are refactored.
--- This is just to ensure the chromatic number exists.
-theorem IsClique.card_le_chromaticNumber [Finite V] {s : Finset V} (h : G.IsClique s) :
+theorem IsClique.card_le_chromaticNumber {s : Finset V} (h : G.IsClique s) :
     s.card ≤ G.chromaticNumber := by
-  cases nonempty_fintype V
-  exact h.card_le_of_colorable G.colorable_chromaticNumber_of_fintype
+  obtain (hc | hc) := eq_or_ne G.chromaticNumber ⊤
+  · rw [hc]
+    exact le_top
+  · have hc' := hc
+    rw [chromaticNumber_ne_top_iff_exists] at hc'
+    obtain ⟨n, c⟩ := hc'
+    rw [← ENat.coe_toNat_eq_self] at hc
+    rw [← hc, Nat.cast_le]
+    exact h.card_le_of_colorable (colorable_chromaticNumber c)
 #align simple_graph.is_clique.card_le_chromatic_number SimpleGraph.IsClique.card_le_chromaticNumber
 
 protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n < m) :
@@ -449,11 +487,15 @@ protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n
   exact Nat.lt_le_asymm hm (h.card_le_of_colorable hc)
 #align simple_graph.colorable.clique_free SimpleGraph.Colorable.cliqueFree
 
--- TODO eliminate `Finite V` constraint once chromatic numbers are refactored.
--- This is just to ensure the chromatic number exists.
-theorem cliqueFree_of_chromaticNumber_lt [Finite V] {n : ℕ} (hc : G.chromaticNumber < n) :
-    G.CliqueFree n :=
-  G.colorable_chromaticNumber_of_fintype.cliqueFree hc
+theorem cliqueFree_of_chromaticNumber_lt {n : ℕ} (hc : G.chromaticNumber < n) :
+    G.CliqueFree n := by
+  have hne : G.chromaticNumber ≠ ⊤ := hc.ne_top
+  obtain ⟨m, hc'⟩ := chromaticNumber_ne_top_iff_exists.mp hne
+  have := colorable_chromaticNumber hc'
+  refine this.cliqueFree ?_
+  rw [← ENat.coe_toNat_eq_self] at hne
+  rw [← hne] at hc
+  simpa using hc
 #align simple_graph.clique_free_of_chromatic_number_lt SimpleGraph.cliqueFree_of_chromaticNumber_lt
 
 end SimpleGraph

70fd9563

fix: patch for std4#194 (more order lemmas for Nat) (#8077)

5f84b04f

Diff

@@ -351,7 +351,7 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
     specialize h (G.recolorOfEmbedding f C')
     have h1 : Function.Surjective f := Function.Surjective.of_comp h
     have h2 := Fintype.card_le_of_surjective _ h1
-    exact Nat.lt_le_antisymm hc h2
+    exact Nat.lt_le_asymm hc h2
 #align simple_graph.chromatic_number_eq_card_of_forall_surj SimpleGraph.chromaticNumber_eq_card_of_forall_surj
 
 theorem chromaticNumber_bot [Nonempty V] : (⊥ : SimpleGraph V).chromaticNumber = 1 := by
@@ -446,7 +446,7 @@ protected theorem Colorable.cliqueFree {n m : ℕ} (hc : G.Colorable n) (hm : n
   by_contra h
   simp only [CliqueFree, isNClique_iff, not_forall, Classical.not_not] at h
   obtain ⟨s, h, rfl⟩ := h
-  exact Nat.lt_le_antisymm hm (h.card_le_of_colorable hc)
+  exact Nat.lt_le_asymm hm (h.card_le_of_colorable hc)
 #align simple_graph.colorable.clique_free SimpleGraph.Colorable.cliqueFree
 
 -- TODO eliminate `Finite V` constraint once chromatic numbers are refactored.

70fd9563

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -163,7 +163,7 @@ noncomputable def chromaticNumber : ℕ :=
 #align simple_graph.chromatic_number SimpleGraph.chromaticNumber
 
 /-- Given an embedding, there is an induced embedding of colorings. -/
-def recolorOfEmbedding {α β : Type _} (f : α ↪ β) : G.Coloring α ↪ G.Coloring β where
+def recolorOfEmbedding {α β : Type*} (f : α ↪ β) : G.Coloring α ↪ G.Coloring β where
   toFun C := (Embedding.completeGraph f).toHom.comp C
   inj' := by -- this was strangely painful; seems like missing lemmas about embeddings
     intro C C' h
@@ -176,7 +176,7 @@ def recolorOfEmbedding {α β : Type _} (f : α ↪ β) : G.Coloring α ↪ G.Co
 #align simple_graph.recolor_of_embedding SimpleGraph.recolorOfEmbedding
 
 /-- Given an equivalence, there is an induced equivalence between colorings. -/
-def recolorOfEquiv {α β : Type _} (f : α ≃ β) : G.Coloring α ≃ G.Coloring β where
+def recolorOfEquiv {α β : Type*} (f : α ≃ β) : G.Coloring α ≃ G.Coloring β where
   toFun := G.recolorOfEmbedding f.toEmbedding
   invFun := G.recolorOfEmbedding f.symm.toEmbedding
   left_inv C := by
@@ -189,7 +189,7 @@ def recolorOfEquiv {α β : Type _} (f : α ≃ β) : G.Coloring α ≃ G.Colori
 
 /-- There is a noncomputable embedding of `α`-colorings to `β`-colorings if
 `β` has at least as large a cardinality as `α`. -/
-noncomputable def recolorOfCardLE {α β : Type _} [Fintype α] [Fintype β]
+noncomputable def recolorOfCardLE {α β : Type*} [Fintype α] [Fintype β]
     (hn : Fintype.card α ≤ Fintype.card β) : G.Coloring α ↪ G.Coloring β :=
   G.recolorOfEmbedding <| (Function.Embedding.nonempty_of_card_le hn).some
 #align simple_graph.recolor_of_card_le SimpleGraph.recolorOfCardLE
@@ -215,7 +215,7 @@ noncomputable def Colorable.toColoring [Fintype α] {n : ℕ} (hc : G.Colorable
   exact G.recolorOfCardLE hn hc.some
 #align simple_graph.colorable.to_coloring SimpleGraph.Colorable.toColoring
 
-theorem Colorable.of_embedding {V' : Type _} {G' : SimpleGraph V'} (f : G ↪g G') {n : ℕ}
+theorem Colorable.of_embedding {V' : Type*} {G' : SimpleGraph V'} (f : G ↪g G') {n : ℕ}
     (h : G'.Colorable n) : G.Colorable n :=
   ⟨(h.toColoring (by simp)).comp f⟩
 #align simple_graph.colorable.of_embedding SimpleGraph.Colorable.of_embedding
@@ -319,7 +319,7 @@ theorem Colorable.mono_left {G' : SimpleGraph V} (h : G ≤ G') {n : ℕ} (hc :
   ⟨hc.some.comp (Hom.mapSpanningSubgraphs h)⟩
 #align simple_graph.colorable.mono_left SimpleGraph.Colorable.mono_left
 
-theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGraph V'} {m : ℕ}
+theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type*} {G' : SimpleGraph V'} {m : ℕ}
     (hc : G'.Colorable m) (h : ∀ n, G'.Colorable n → G.Colorable n) :
     G.chromaticNumber ≤ G'.chromaticNumber := by
   apply csInf_le chromaticNumber_bddBelow
@@ -332,7 +332,7 @@ theorem Colorable.chromaticNumber_mono (G' : SimpleGraph V) {m : ℕ} (hc : G'.C
   hc.chromaticNumber_le_of_forall_imp fun _ => Colorable.mono_left h
 #align simple_graph.colorable.chromatic_number_mono SimpleGraph.Colorable.chromaticNumber_mono
 
-theorem Colorable.chromaticNumber_mono_of_embedding {V' : Type _} {G' : SimpleGraph V'} {n : ℕ}
+theorem Colorable.chromaticNumber_mono_of_embedding {V' : Type*} {G' : SimpleGraph V'} {n : ℕ}
     (h : G'.Colorable n) (f : G ↪g G') : G.chromaticNumber ≤ G'.chromaticNumber :=
   h.chromaticNumber_le_of_forall_imp fun _ => Colorable.of_embedding f
 #align simple_graph.colorable.chromatic_number_mono_of_embedding SimpleGraph.Colorable.chromaticNumber_mono_of_embedding
@@ -373,7 +373,7 @@ theorem chromaticNumber_top [Fintype V] : (⊤ : SimpleGraph V).chromaticNumber
   exact C.valid h
 #align simple_graph.chromatic_number_top SimpleGraph.chromaticNumber_top
 
-theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
+theorem chromaticNumber_top_eq_zero_of_infinite (V : Type*) [Infinite V] :
     (⊤ : SimpleGraph V).chromaticNumber = 0 := by
   let n := (⊤ : SimpleGraph V).chromaticNumber
   by_contra hc
@@ -389,14 +389,14 @@ theorem chromaticNumber_top_eq_zero_of_infinite (V : Type _) [Infinite V] :
 
 /-- The bicoloring of a complete bipartite graph using whether a vertex
 is on the left or on the right. -/
-def CompleteBipartiteGraph.bicoloring (V W : Type _) : (completeBipartiteGraph V W).Coloring Bool :=
+def CompleteBipartiteGraph.bicoloring (V W : Type*) : (completeBipartiteGraph V W).Coloring Bool :=
   Coloring.mk (fun v => v.isRight)
     (by
       intro v w
       cases v <;> cases w <;> simp)
 #align simple_graph.complete_bipartite_graph.bicoloring SimpleGraph.CompleteBipartiteGraph.bicoloring
 
-theorem CompleteBipartiteGraph.chromaticNumber {V W : Type _} [Nonempty V] [Nonempty W] :
+theorem CompleteBipartiteGraph.chromaticNumber {V W : Type*} [Nonempty V] [Nonempty W] :
     (completeBipartiteGraph V W).chromaticNumber = 2 := by
   apply chromaticNumber_eq_card_of_forall_surj (CompleteBipartiteGraph.bicoloring V W)
   intro C b

70fd9563

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2021 Arthur Paulino. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.coloring
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Combinatorics.SimpleGraph.Clique
 import Mathlib.Data.Nat.Lattice
 import Mathlib.Data.Setoid.Partition
 import Mathlib.Order.Antichain
 
+#align_import combinatorics.simple_graph.coloring from "leanprover-community/mathlib"@"70fd9563a21e7b963887c9360bd29b2393e6225a"
+
 /-!
 # Graph Coloring

70fd9563

chore: bump to nightly-2023-07-01 (#5409)

depends on: https://github.com/leanprover/std4/pull/163
depends on: #5584
depends on: #5715
depends on: #5729
depends on: https://github.com/leanprover/std4/pull/173

Co-authored-by: Komyyy <pol_tta@outlook.jp> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

906f7221

Diff

@@ -305,7 +305,7 @@ theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.
   apply le_csInf (colorable_set_nonempty_of_colorable hc)
   intro m hm
   by_contra h'
-  simp only [not_le, Nat.lt_one_iff] at h'
+  simp only [not_le] at h'
   obtain ⟨i, hi⟩ := hm.some (Classical.arbitrary V)
   have h₁: i < 0 := lt_of_lt_of_le hi (Nat.le_of_lt_succ h')
   exact Nat.not_lt_zero _ h₁

70fd9563

chore: Rename to sSup/iSup (#3938)

As discussed on Zulip

Renames

supₛ → sSup
infₛ → sInf
supᵢ → iSup
infᵢ → iInf
bsupₛ → bsSup
binfₛ → bsInf
bsupᵢ → biSup
binfᵢ → biInf
csupₛ → csSup
cinfₛ → csInf
csupᵢ → ciSup
cinfᵢ → ciInf
unionₛ → sUnion
interₛ → sInter
unionᵢ → iUnion
interᵢ → iInter
bunionₛ → bsUnion
binterₛ → bsInter
bunionᵢ → biUnion
binterᵢ → biInter

Co-authored-by: Parcly Taxel <reddeloostw@gmail.com>

d1eb6264

Diff

@@ -162,7 +162,7 @@ def selfColoring : G.Coloring V := Coloring.mk id fun {_ _} => G.ne_of_adj
 /-- The chromatic number of a graph is the minimal number of colors needed to color it.
 If `G` isn't colorable with finitely many colors, this will be 0. -/
 noncomputable def chromaticNumber : ℕ :=
-  infₛ { n : ℕ | G.Colorable n }
+  sInf { n : ℕ | G.Colorable n }
 #align simple_graph.chromatic_number SimpleGraph.chromaticNumber
 
 /-- Given an embedding, there is an induced embedding of colorings. -/
@@ -252,20 +252,20 @@ theorem chromaticNumber_bddBelow : BddBelow { n : ℕ | G.Colorable n } :=
 
 theorem chromaticNumber_le_of_colorable {n : ℕ} (hc : G.Colorable n) : G.chromaticNumber ≤ n := by
   rw [chromaticNumber]
-  apply cinfₛ_le chromaticNumber_bddBelow
+  apply csInf_le chromaticNumber_bddBelow
   constructor
   exact Classical.choice hc
 #align simple_graph.chromatic_number_le_of_colorable SimpleGraph.chromaticNumber_le_of_colorable
 
 theorem chromaticNumber_le_card [Fintype α] (C : G.Coloring α) :
     G.chromaticNumber ≤ Fintype.card α :=
-  cinfₛ_le chromaticNumber_bddBelow C.to_colorable
+  csInf_le chromaticNumber_bddBelow C.to_colorable
 #align simple_graph.chromatic_number_le_card SimpleGraph.chromaticNumber_le_card
 
 theorem colorable_chromaticNumber {m : ℕ} (hc : G.Colorable m) : G.Colorable G.chromaticNumber := by
   classical
   dsimp only [chromaticNumber]
-  rw [Nat.infₛ_def]
+  rw [Nat.sInf_def]
   apply Nat.find_spec
   exact colorable_set_nonempty_of_colorable hc
 #align simple_graph.colorable_chromatic_number SimpleGraph.colorable_chromaticNumber
@@ -279,7 +279,7 @@ theorem colorable_chromaticNumber_of_fintype (G : SimpleGraph V) [Finite V] :
 theorem chromaticNumber_le_one_of_subsingleton (G : SimpleGraph V) [Subsingleton V] :
     G.chromaticNumber ≤ 1 := by
   rw [chromaticNumber]
-  apply cinfₛ_le chromaticNumber_bddBelow
+  apply csInf_le chromaticNumber_bddBelow
   constructor
   refine' Coloring.mk (fun _ => 0) _
   intro v w
@@ -290,7 +290,7 @@ theorem chromaticNumber_le_one_of_subsingleton (G : SimpleGraph V) [Subsingleton
 theorem chromaticNumber_eq_zero_of_isempty (G : SimpleGraph V) [IsEmpty V] :
     G.chromaticNumber = 0 := by
   rw [← nonpos_iff_eq_zero]
-  apply cinfₛ_le chromaticNumber_bddBelow
+  apply csInf_le chromaticNumber_bddBelow
   apply colorable_of_isEmpty
 #align simple_graph.chromatic_number_eq_zero_of_isempty SimpleGraph.chromaticNumber_eq_zero_of_isempty
 
@@ -302,7 +302,7 @@ theorem isEmpty_of_chromaticNumber_eq_zero (G : SimpleGraph V) [Finite V]
 #align simple_graph.is_empty_of_chromatic_number_eq_zero SimpleGraph.isEmpty_of_chromaticNumber_eq_zero
 
 theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.chromaticNumber := by
-  apply le_cinfₛ (colorable_set_nonempty_of_colorable hc)
+  apply le_csInf (colorable_set_nonempty_of_colorable hc)
   intro m hm
   by_contra h'
   simp only [not_le, Nat.lt_one_iff] at h'
@@ -313,7 +313,7 @@ theorem chromaticNumber_pos [Nonempty V] {n : ℕ} (hc : G.Colorable n) : 0 < G.
 
 theorem colorable_of_chromaticNumber_pos (h : 0 < G.chromaticNumber) :
     G.Colorable G.chromaticNumber := by
-  obtain ⟨h, hn⟩ := Nat.nonempty_of_pos_infₛ h
+  obtain ⟨h, hn⟩ := Nat.nonempty_of_pos_sInf h
   exact colorable_chromaticNumber hn
 #align simple_graph.colorable_of_chromatic_number_pos SimpleGraph.colorable_of_chromaticNumber_pos
 
@@ -325,7 +325,7 @@ theorem Colorable.mono_left {G' : SimpleGraph V} (h : G ≤ G') {n : ℕ} (hc :
 theorem Colorable.chromaticNumber_le_of_forall_imp {V' : Type _} {G' : SimpleGraph V'} {m : ℕ}
     (hc : G'.Colorable m) (h : ∀ n, G'.Colorable n → G.Colorable n) :
     G.chromaticNumber ≤ G'.chromaticNumber := by
-  apply cinfₛ_le chromaticNumber_bddBelow
+  apply csInf_le chromaticNumber_bddBelow
   apply h
   apply colorable_chromaticNumber hc
 #align simple_graph.colorable.chromatic_number_le_of_forall_imp SimpleGraph.Colorable.chromaticNumber_le_of_forall_imp
@@ -347,7 +347,7 @@ theorem chromaticNumber_eq_card_of_forall_surj [Fintype α] (C : G.Coloring α)
   · by_contra hc
     rw [not_le] at hc
     obtain ⟨n, cn, hc⟩ :=
-      exists_lt_of_cinfₛ_lt (colorable_set_nonempty_of_colorable C.to_colorable) hc
+      exists_lt_of_csInf_lt (colorable_set_nonempty_of_colorable C.to_colorable) hc
     rw [← Fintype.card_fin n] at hc
     have f := (Function.Embedding.nonempty_of_card_le (le_of_lt hc)).some
     have C' := cn.some

70fd9563

fix: remove stray LibrarySearch import in Combinatorics.SimpleGraph.Coloring (#2681)

Removes unneeded import left behind from https://github.com/leanprover-community/mathlib4/pull/2526.

2d32876a

Diff

@@ -12,7 +12,6 @@ import Mathlib.Combinatorics.SimpleGraph.Clique
 import Mathlib.Data.Nat.Lattice
 import Mathlib.Data.Setoid.Partition
 import Mathlib.Order.Antichain
-import Mathlib.Tactic.LibrarySearch -- porting notes: TODO REMOVE
 
 /-!
 # Graph Coloring

70fd9563

feat: tactic congr! and improvement to convert (#2566)

This introduces a tactic congr! that is an analogue to mathlib 3's congr'. It is a more insistent version of congr that makes use of more congruence lemmas (including user congruence lemmas), propext, funext, and Subsingleton instances. It also has a feature to lift reflexive relations to equalities. Along with funext, the tactic does intros, allowing congr! to get access to function bodies; the introduced variables can be named using rename_i if needed.

This also modifies convert to use congr! rather than congr, which makes it work more like the mathlib3 version of the tactic.

b46c2e36

Diff

@@ -118,8 +118,6 @@ theorem Coloring.card_colorClasses_le [Fintype α] [Fintype C.colorClasses] :
   -- porting note: brute force instance declaration `[Fintype (Setoid.classes (Setoid.ker C))]`
   haveI : Fintype (Setoid.classes (Setoid.ker C)) := by assumption
   convert Setoid.card_classes_ker_le C
-  -- porting note: convert would have handled this already in Lean 3:
-  apply Subsingleton.elim
 #align simple_graph.coloring.card_color_classes_le SimpleGraph.Coloring.card_colorClasses_le
 
 theorem Coloring.not_adj_of_mem_colorClass {c : α} {v w : V} (hv : v ∈ C.colorClass c)

70fd9563

feat Port/Combinatorics.SimpleGraph.Coloring (#2526)

Co-authored-by: Kyle Miller <kmill31415@gmail.com>

03cb3af0

`combinatorics.simple_graph.coloring` ⟷ `Mathlib.Combinatorics.SimpleGraph.Coloring`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Renames

Dependencies 7 + 250

combinatorics.simple_graph.coloring ⟷ Mathlib.Combinatorics.SimpleGraph.Coloring

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Renames

Dependencies 7 + 250

`combinatorics.simple_graph.coloring` ⟷ `Mathlib.Combinatorics.SimpleGraph.Coloring`