PR contents

(last sync)

feat(combinatorics/simple_graph): More clique lemmas (#19203)

More lemmas about is_clique, is_n_clique, edge_set. Also define clique_free_on, a local version of clique_free.

Diff

@@ -5,6 +5,7 @@ Authors: Yaël Dillies, Bhavik Mehta
 -/
 import combinatorics.simple_graph.basic
 import data.finset.pairwise
+import data.finset.preimage
 
 /-!
 # Graph cliques
@@ -25,13 +26,13 @@ adjacent.
 ## TODO
 
 * Clique numbers
-* Do we need `clique_set`, a version of `clique_finset` for infinite graphs?
+* Dualise all the API to get independent sets
 -/
 
-open finset fintype
+open finset fintype function
 
 namespace simple_graph
-variables {α : Type*} (G H : simple_graph α)
+variables {α β : Type*} (G H : simple_graph α)
 
 /-! ### Cliques -/
 
@@ -61,13 +62,33 @@ end
 instance [decidable_eq α] [decidable_rel G.adj] {s : finset α} : decidable (G.is_clique s) :=
 decidable_of_iff' _ G.is_clique_iff
 
-variables {G H}
+variables {G H} {a b : α}
+
+@[simp] lemma is_clique_empty : G.is_clique ∅ := set.pairwise_empty _
+@[simp] lemma is_clique_singleton (a : α) : G.is_clique {a} := set.pairwise_singleton _ _
+
+lemma is_clique_pair : G.is_clique {a, b} ↔ a ≠ b → G.adj a b :=
+set.pairwise_pair_of_symmetric G.symm
+
+@[simp] lemma is_clique_insert :
+  G.is_clique (insert a s) ↔ G.is_clique s ∧ ∀ b ∈ s, a ≠ b → G.adj a b :=
+set.pairwise_insert_of_symmetric G.symm
 
-lemma is_clique.mono (h : G ≤ H) : G.is_clique s → H.is_clique s :=
-by { simp_rw is_clique_iff, exact set.pairwise.mono' h }
+lemma is_clique_insert_of_not_mem (ha : a ∉ s) :
+  G.is_clique (insert a s) ↔ G.is_clique s ∧ ∀ b ∈ s, G.adj a b :=
+set.pairwise_insert_of_symmetric_of_not_mem G.symm ha
 
-lemma is_clique.subset (h : t ⊆ s) : G.is_clique s → G.is_clique t :=
-by { simp_rw is_clique_iff, exact set.pairwise.mono h }
+lemma is_clique.insert (hs : G.is_clique s) (h : ∀ b ∈ s, a ≠ b → G.adj a b) :
+  G.is_clique (insert a s) :=
+hs.insert_of_symmetric G.symm h
+
+lemma is_clique.mono (h : G ≤ H) : G.is_clique s → H.is_clique s := set.pairwise.mono' h
+lemma is_clique.subset (h : t ⊆ s) : G.is_clique s → G.is_clique t := set.pairwise.mono h
+
+protected lemma is_clique.map {G : simple_graph α} {s : set α} (h : G.is_clique s) {f : α ↪ β} :
+  (G.map f).is_clique (f '' s) :=
+by { rintro _ ⟨a, ha, rfl⟩ _ ⟨b, hb, rfl⟩ hab,
+  exact ⟨a, b, h ha hb $ ne_of_apply_ne _ hab, rfl, rfl⟩ }
 
 @[simp] lemma is_clique_bot_iff : (⊥ : simple_graph α).is_clique s ↔ (s : set α).subsingleton :=
 set.pairwise_bot_iff
@@ -93,11 +114,19 @@ instance [decidable_eq α] [decidable_rel G.adj] {n : ℕ} {s : finset α} :
   decidable (G.is_n_clique n s) :=
 decidable_of_iff' _ G.is_n_clique_iff
 
-variables {G H}
+variables {G H} {a b c : α}
+
+@[simp] lemma is_n_clique_empty : G.is_n_clique n ∅ ↔ n = 0 := by simp [is_n_clique_iff, eq_comm]
+@[simp] lemma is_n_clique_singleton : G.is_n_clique n {a} ↔ n = 1 :=
+by simp [is_n_clique_iff, eq_comm]
 
 lemma is_n_clique.mono (h : G ≤ H) : G.is_n_clique n s → H.is_n_clique n s :=
 by { simp_rw is_n_clique_iff, exact and.imp_left (is_clique.mono h) }
 
+protected lemma is_n_clique.map (h : G.is_n_clique n s) {f : α ↪ β} :
+  (G.map f).is_n_clique n (s.map f) :=
+⟨by { rw coe_map, exact h.1.map}, (card_map _).trans h.2⟩
+
 @[simp] lemma is_n_clique_bot_iff : (⊥ : simple_graph α).is_n_clique n s ↔ n ≤ 1 ∧ s.card = n :=
 begin
   rw [is_n_clique_iff, is_clique_bot_iff],
@@ -106,7 +135,22 @@ begin
   exact card_le_one.symm,
 end
 
-variables [decidable_eq α] {a b c : α}
+@[simp] lemma is_n_clique_zero : G.is_n_clique 0 s ↔ s = ∅ :=
+by { simp only [is_n_clique_iff, finset.card_eq_zero, and_iff_right_iff_imp], rintro rfl, simp }
+
+@[simp] lemma is_n_clique_one : G.is_n_clique 1 s ↔ ∃ a, s = {a} :=
+by { simp only [is_n_clique_iff, card_eq_one, and_iff_right_iff_imp], rintro ⟨a, rfl⟩, simp }
+
+variables [decidable_eq α]
+
+lemma is_n_clique.insert (hs : G.is_n_clique n s) (h : ∀ b ∈ s, G.adj a b) :
+  G.is_n_clique (n + 1) (insert a s) :=
+begin
+  split,
+  { push_cast,
+    exact hs.1.insert (λ b hb _, h _ hb) },
+  { rw [card_insert_of_not_mem (λ ha, (h _ ha).ne rfl), hs.2] }
+end
 
 lemma is_3_clique_triple_iff : G.is_n_clique 3 {a, b, c} ↔ G.adj a b ∧ G.adj a c ∧ G.adj b c :=
 begin
@@ -193,7 +237,7 @@ begin
   use (iso.complete_graph (fintype.equiv_fin α)).symm.to_embedding.trans f,
 end
 
-lemma clique_free_bot (h : 2 ≤ n) : (⊥ : simple_graph α).clique_free n :=
+@[simp] lemma clique_free_bot (h : 2 ≤ n) : (⊥ : simple_graph α).clique_free n :=
 begin
   rintro t ht,
   rw is_n_clique_bot_iff at ht,
@@ -219,8 +263,77 @@ begin
   simpa using fintype.card_le_of_embedding h.some.to_embedding,
 end
 
+@[simp] lemma clique_free_two : G.clique_free 2 ↔ G = ⊥ :=
+begin
+  classical,
+  split,
+  { simp_rw [←edge_set_eq_empty, set.eq_empty_iff_forall_not_mem, sym2.forall, mem_edge_set],
+    exact λ h a b hab, h _ ⟨by simpa [hab.ne], card_doubleton hab.ne⟩ },
+  { rintro rfl,
+    exact clique_free_bot le_rfl }
+end
+
 end clique_free
 
+section clique_free_on
+variables {s s₁ s₂ : set α} {t : finset α} {a b : α} {m n : ℕ}
+
+/-- `G.clique_free_on s n` means that `G` has no `n`-cliques contained in `s`. -/
+def clique_free_on (G : simple_graph α) (s : set α) (n : ℕ) : Prop :=
+∀ ⦃t⦄, ↑t ⊆ s → ¬G.is_n_clique n t
+
+lemma clique_free_on.subset (hs : s₁ ⊆ s₂) (h₂ : G.clique_free_on s₂ n) : G.clique_free_on s₁ n :=
+λ t hts, h₂ $ hts.trans hs
+
+lemma clique_free_on.mono (hmn : m ≤ n) (hG : G.clique_free_on s m) : G.clique_free_on s n :=
+begin
+  rintro t hts ht,
+  obtain ⟨u, hut, hu⟩ := t.exists_smaller_set _ (hmn.trans ht.card_eq.ge),
+  exact hG ((coe_subset.2 hut).trans hts) ⟨ht.clique.subset hut, hu⟩,
+end
+
+lemma clique_free_on.anti (hGH : G ≤ H) (hH : H.clique_free_on s n) : G.clique_free_on s n :=
+λ t hts ht, hH hts $ ht.mono hGH
+
+@[simp] lemma clique_free_on_empty : G.clique_free_on ∅ n ↔ n ≠ 0 :=
+by simp [clique_free_on, set.subset_empty_iff]
+
+@[simp] lemma clique_free_on_singleton : G.clique_free_on {a} n ↔ 1 < n :=
+by obtain _ | _ | n := n; simp [clique_free_on, set.subset_singleton_iff_eq]
+
+@[simp] lemma clique_free_on_univ : G.clique_free_on set.univ n ↔ G.clique_free n :=
+by simp [clique_free, clique_free_on]
+
+protected lemma clique_free.clique_free_on (hG : G.clique_free n) : G.clique_free_on s n :=
+λ t _, hG _
+
+lemma clique_free_on_of_card_lt {s : finset α} (h : s.card < n) : G.clique_free_on s n :=
+λ t hts ht, h.not_le $ ht.2.symm.trans_le $ card_mono hts
+
+--TOOD: Restate using `simple_graph.indep_set` once we have it
+@[simp] lemma clique_free_on_two : G.clique_free_on s 2 ↔ s.pairwise G.adjᶜ :=
+begin
+  classical,
+  refine ⟨λ h a ha b hb _ hab, h _ ⟨by simpa [hab.ne], card_doubleton hab.ne⟩, _⟩,
+  { push_cast,
+    exact set.insert_subset.2 ⟨ha, set.singleton_subset_iff.2 hb⟩ },
+  simp only [clique_free_on, is_n_clique_iff, card_eq_two, coe_subset, not_and, not_exists],
+  rintro h t hst ht a b hab rfl,
+  simp only [coe_insert, coe_singleton, set.insert_subset, set.singleton_subset_iff] at hst,
+  refine h hst.1 hst.2 hab (ht _ _ hab); simp,
+end
+
+lemma clique_free_on.of_succ (hs : G.clique_free_on s (n + 1)) (ha : a ∈ s) :
+  G.clique_free_on (s ∩ G.neighbor_set a) n :=
+begin
+  classical,
+  refine λ t hts ht, hs _ (ht.insert $ λ b hb, (hts hb).2),
+  push_cast,
+  exact set.insert_subset.2 ⟨ha, hts.trans $ set.inter_subset_left _ _⟩,
+end
+
+end clique_free_on
+
 /-! ### Set of cliques -/
 
 section clique_set
@@ -229,22 +342,60 @@ variables (G) {n : ℕ} {a b c : α} {s : finset α}
 /-- The `n`-cliques in a graph as a set. -/
 def clique_set (n : ℕ) : set (finset α) := {s | G.is_n_clique n s}
 
-lemma mem_clique_set_iff : s ∈ G.clique_set n ↔ G.is_n_clique n s := iff.rfl
+@[simp] lemma mem_clique_set_iff : s ∈ G.clique_set n ↔ G.is_n_clique n s := iff.rfl
 
 @[simp] lemma clique_set_eq_empty_iff : G.clique_set n = ∅ ↔ G.clique_free n :=
 by simp_rw [clique_free, set.eq_empty_iff_forall_not_mem, mem_clique_set_iff]
 
-alias clique_set_eq_empty_iff ↔ _ clique_free.clique_set
-
-attribute [protected] clique_free.clique_set
-
 variables {G H}
 
+protected lemma clique_free.clique_set : G.clique_free n → G.clique_set n = ∅ :=
+G.clique_set_eq_empty_iff.2
+
 @[mono] lemma clique_set_mono (h : G ≤ H) : G.clique_set n ⊆ H.clique_set n :=
 λ _, is_n_clique.mono h
 
 lemma clique_set_mono' (h : G ≤ H) : G.clique_set ≤ H.clique_set := λ _, clique_set_mono h
 
+@[simp] lemma clique_set_zero (G : simple_graph α) : G.clique_set 0 = {∅} :=
+set.ext $ λ s, by simp
+
+@[simp] lemma clique_set_one (G : simple_graph α) : G.clique_set 1 = set.range singleton :=
+set.ext $ λ s, by simp [eq_comm]
+
+@[simp] lemma clique_set_bot (hn : 1 < n) : (⊥ : simple_graph α).clique_set n = ∅ :=
+(clique_free_bot hn).clique_set
+
+@[simp] lemma clique_set_map (hn : n ≠ 1) (G : simple_graph α) (f : α ↪ β) :
+  (G.map f).clique_set n = map f '' G.clique_set n :=
+begin
+  ext s,
+  split,
+  { rintro ⟨hs, rfl⟩,
+    have hs' : (s.preimage f $ f.injective.inj_on _).map f = s,
+    { classical,
+      rw [map_eq_image, image_preimage, filter_true_of_mem],
+      rintro a ha,
+      obtain ⟨b, hb, hba⟩ := exists_mem_ne (hn.lt_of_le' $ finset.card_pos.2 ⟨a, ha⟩) a,
+      obtain ⟨c, _, _, hc, _⟩ := hs ha hb hba.symm,
+      exact ⟨c, hc⟩ },
+    refine ⟨s.preimage f $ f.injective.inj_on _, ⟨_, by rw [←card_map f, hs']⟩, hs'⟩,
+    rw coe_preimage,
+    exact λ a ha b hb hab, map_adj_apply.1 (hs ha hb $ f.injective.ne hab) },
+  { rintro ⟨s, hs, rfl⟩,
+    exact is_n_clique.map hs }
+end
+
+@[simp] lemma clique_set_map_of_equiv (G : simple_graph α) (e : α ≃ β) (n : ℕ) :
+  (G.map e.to_embedding).clique_set n = map e.to_embedding '' G.clique_set n :=
+begin
+  obtain rfl | hn := eq_or_ne n 1,
+  { ext,
+    simp [e.exists_congr_left] },
+  { exact clique_set_map hn _ _ }
+end
+
+
 end clique_set
 
 /-! ### Finset of cliques -/
@@ -255,10 +406,11 @@ variables (G) [fintype α] [decidable_eq α] [decidable_rel G.adj] {n : ℕ} {a
 /-- The `n`-cliques in a graph as a finset. -/
 def clique_finset (n : ℕ) : finset (finset α) := univ.filter $ G.is_n_clique n
 
-lemma mem_clique_finset_iff : s ∈ G.clique_finset n ↔ G.is_n_clique n s :=
+@[simp] lemma mem_clique_finset_iff : s ∈ G.clique_finset n ↔ G.is_n_clique n s :=
 mem_filter.trans $ and_iff_right $ mem_univ _
 
-@[simp] lemma coe_clique_finset (n : ℕ) : (G.clique_finset n : set (finset α)) = G.clique_set n :=
+@[simp, norm_cast] lemma coe_clique_finset (n : ℕ) :
+  (G.clique_finset n : set (finset α)) = G.clique_set n :=
 set.ext $ λ _, mem_clique_finset_iff _
 
 @[simp] lemma clique_finset_eq_empty_iff : G.clique_finset n = ∅ ↔ G.clique_free n :=
@@ -268,10 +420,31 @@ alias clique_finset_eq_empty_iff ↔ _ _root_.simple_graph.clique_free.clique_fi
 
 attribute [protected] clique_free.clique_finset
 
-variables {G} [decidable_rel H.adj]
+variables {G}
+
+lemma card_clique_finset_le : (G.clique_finset n).card ≤ (card α).choose n :=
+begin
+  rw [←card_univ, ←card_powerset_len],
+  refine card_mono (λ s, _),
+  simpa [mem_powerset_len_univ_iff] using is_n_clique.card_eq,
+end
+
+variables [decidable_rel H.adj]
 
 @[mono] lemma clique_finset_mono (h : G ≤ H) : G.clique_finset n ⊆ H.clique_finset n :=
 monotone_filter_right _ $ λ _, is_n_clique.mono h
 
+variables [fintype β] [decidable_eq β] (G)
+
+@[simp] lemma clique_finset_map (f : α ↪ β) (hn : n ≠ 1) :
+  (G.map f).clique_finset n = (G.clique_finset n).map ⟨map f, finset.map_injective _⟩ :=
+coe_injective $
+  by simp_rw [coe_clique_finset, clique_set_map hn, coe_map, coe_clique_finset, embedding.coe_fn_mk]
+
+@[simp] lemma clique_finset_map_of_equiv (e : α ≃ β) (n : ℕ) :
+  (G.map e.to_embedding).clique_finset n =
+    (G.clique_finset n).map ⟨map e.to_embedding, finset.map_injective _⟩ :=
+coe_injective $ by push_cast; exact clique_set_map_of_equiv _ _ _
+
 end clique_finset
 end simple_graph

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -260,7 +260,7 @@ theorem is3Clique_iff :
   refine' ⟨fun h => _, _⟩
   · obtain ⟨a, b, c, -, -, -, rfl⟩ := card_eq_three.1 h.card_eq
     refine' ⟨a, b, c, _⟩
-    rw [is_3_clique_triple_iff] at h 
+    rw [is_3_clique_triple_iff] at h
     tauto
   · rintro ⟨a, b, c, hab, hbc, hca, rfl⟩
     exact is_3_clique_triple_iff.2 ⟨hab, hbc, hca⟩
@@ -300,7 +300,7 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   simp only [card_map, Finset.card_fin, eq_self_iff_true, and_true_iff]
   ext ⟨v, hv⟩ ⟨w, hw⟩
   simp only [coe_map, RelEmbedding.coe_toEmbedding, Set.mem_image, coe_univ, Set.mem_univ,
-    true_and_iff] at hv hw 
+    true_and_iff] at hv hw
   obtain ⟨v', rfl⟩ := hv
   obtain ⟨w', rfl⟩ := hw
   simp only [f.map_adj_iff, comap_adj, Function.Embedding.coe_subtype, Subtype.coe_mk, top_adj,
@@ -315,13 +315,13 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     (⊤ : SimpleGraph (Fin n)) ↪g G :=
   by
   simp only [clique_free, is_n_clique_iff, is_clique_iff_induce_eq, Classical.not_forall,
-    Classical.not_not] at h 
+    Classical.not_not] at h
   obtain ⟨ha, hb⟩ := h.some_spec
   have : (⊤ : SimpleGraph (Fin h.some.card)) ≃g (⊤ : SimpleGraph h.some) :=
     by
     apply iso.complete_graph
     simpa using (Fintype.equivFin h.some).symm
-  rw [← ha] at this 
+  rw [← ha] at this
   convert (embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
 #align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFree
 -/
@@ -355,7 +355,7 @@ theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGrap
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n :=
   by
   rintro t ht
-  rw [is_n_clique_bot_iff] at ht 
+  rw [is_n_clique_bot_iff] at ht
   linarith
 #align simple_graph.clique_free_bot SimpleGraph.cliqueFree_bot
 -/
@@ -381,7 +381,7 @@ theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :
   by
   by_contra h
   refine' Nat.lt_le_asymm hc _
-  rw [clique_free_iff, not_isEmpty_iff] at h 
+  rw [clique_free_iff, not_isEmpty_iff] at h
   simpa using Fintype.card_le_of_embedding h.some.to_embedding
 #align simple_graph.clique_free_of_card_lt SimpleGraph.cliqueFree_of_card_lt
 -/
@@ -475,7 +475,7 @@ theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by
     exact Set.insert_subset_iff.2 ⟨ha, Set.singleton_subset_iff.2 hb⟩
   simp only [clique_free_on, is_n_clique_iff, card_eq_two, coe_subset, not_and, not_exists]
   rintro h t hst ht a b hab rfl
-  simp only [coe_insert, coe_singleton, Set.insert_subset_iff, Set.singleton_subset_iff] at hst 
+  simp only [coe_insert, coe_singleton, Set.insert_subset_iff, Set.singleton_subset_iff] at hst
   refine' h hst.1 hst.2 hab (ht _ _ hab) <;> simp
 #align simple_graph.clique_free_on_two SimpleGraph.cliqueFreeOn_two
 -/

bump to nightly-2024-02-01-06

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

5433bded

Diff

@@ -388,7 +388,13 @@ theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :
 
 #print SimpleGraph.cliqueFree_two /-
 @[simp]
-theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by classical
+theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
+  classical
+  constructor
+  · simp_rw [← edge_set_eq_empty, Set.eq_empty_iff_forall_not_mem, Sym2.forall, mem_edge_set]
+    exact fun h a b hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.Ne⟩
+  · rintro rfl
+    exact clique_free_bot le_rfl
 #align simple_graph.clique_free_two SimpleGraph.cliqueFree_two
 -/
 
@@ -462,13 +468,25 @@ theorem cliqueFreeOn_of_card_lt {s : Finset α} (h : s.card < n) : G.CliqueFreeO
 #print SimpleGraph.cliqueFreeOn_two /-
 --TOOD: Restate using `simple_graph.indep_set` once we have it
 @[simp]
-theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by classical
+theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by
+  classical
+  refine' ⟨fun h a ha b hb _ hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.Ne⟩, _⟩
+  · push_cast
+    exact Set.insert_subset_iff.2 ⟨ha, Set.singleton_subset_iff.2 hb⟩
+  simp only [clique_free_on, is_n_clique_iff, card_eq_two, coe_subset, not_and, not_exists]
+  rintro h t hst ht a b hab rfl
+  simp only [coe_insert, coe_singleton, Set.insert_subset_iff, Set.singleton_subset_iff] at hst 
+  refine' h hst.1 hst.2 hab (ht _ _ hab) <;> simp
 #align simple_graph.clique_free_on_two SimpleGraph.cliqueFreeOn_two
 -/
 
 #print SimpleGraph.CliqueFreeOn.of_succ /-
 theorem CliqueFreeOn.of_succ (hs : G.CliqueFreeOn s (n + 1)) (ha : a ∈ s) :
-    G.CliqueFreeOn (s ∩ G.neighborSet a) n := by classical
+    G.CliqueFreeOn (s ∩ G.neighborSet a) n := by
+  classical
+  refine' fun t hts ht => hs _ (ht.insert fun b hb => (hts hb).2)
+  push_cast
+  exact Set.insert_subset_iff.2 ⟨ha, hts.trans <| Set.inter_subset_left _ _⟩
 #align simple_graph.clique_free_on.of_succ SimpleGraph.CliqueFreeOn.of_succ
 -/
 
@@ -550,7 +568,13 @@ theorem cliqueSet_map (hn : n ≠ 1) (G : SimpleGraph α) (f : α ↪ β) :
   ext s
   constructor
   · rintro ⟨hs, rfl⟩
-    have hs' : (s.preimage f <| f.injective.inj_on _).map f = s := by classical
+    have hs' : (s.preimage f <| f.injective.inj_on _).map f = s := by
+      classical
+      rw [map_eq_image, image_preimage, filter_true_of_mem]
+      rintro a ha
+      obtain ⟨b, hb, hba⟩ := exists_mem_ne (hn.lt_of_le' <| Finset.card_pos.2 ⟨a, ha⟩) a
+      obtain ⟨c, _, _, hc, _⟩ := hs ha hb hba.symm
+      exact ⟨c, hc⟩
     refine' ⟨s.preimage f <| f.injective.inj_on _, ⟨_, by rw [← card_map f, hs']⟩, hs'⟩
     rw [coe_preimage]
     exact fun a ha b hb hab => map_adj_apply.1 (hs ha hb <| f.injective.ne hab)

bump to nightly-2024-01-31-06

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

61100fe9

Diff

@@ -388,13 +388,7 @@ theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :
 
 #print SimpleGraph.cliqueFree_two /-
 @[simp]
-theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
-  classical
-  constructor
-  · simp_rw [← edge_set_eq_empty, Set.eq_empty_iff_forall_not_mem, Sym2.forall, mem_edge_set]
-    exact fun h a b hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.Ne⟩
-  · rintro rfl
-    exact clique_free_bot le_rfl
+theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by classical
 #align simple_graph.clique_free_two SimpleGraph.cliqueFree_two
 -/
 
@@ -468,25 +462,13 @@ theorem cliqueFreeOn_of_card_lt {s : Finset α} (h : s.card < n) : G.CliqueFreeO
 #print SimpleGraph.cliqueFreeOn_two /-
 --TOOD: Restate using `simple_graph.indep_set` once we have it
 @[simp]
-theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by
-  classical
-  refine' ⟨fun h a ha b hb _ hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.Ne⟩, _⟩
-  · push_cast
-    exact Set.insert_subset_iff.2 ⟨ha, Set.singleton_subset_iff.2 hb⟩
-  simp only [clique_free_on, is_n_clique_iff, card_eq_two, coe_subset, not_and, not_exists]
-  rintro h t hst ht a b hab rfl
-  simp only [coe_insert, coe_singleton, Set.insert_subset_iff, Set.singleton_subset_iff] at hst 
-  refine' h hst.1 hst.2 hab (ht _ _ hab) <;> simp
+theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by classical
 #align simple_graph.clique_free_on_two SimpleGraph.cliqueFreeOn_two
 -/
 
 #print SimpleGraph.CliqueFreeOn.of_succ /-
 theorem CliqueFreeOn.of_succ (hs : G.CliqueFreeOn s (n + 1)) (ha : a ∈ s) :
-    G.CliqueFreeOn (s ∩ G.neighborSet a) n := by
-  classical
-  refine' fun t hts ht => hs _ (ht.insert fun b hb => (hts hb).2)
-  push_cast
-  exact Set.insert_subset_iff.2 ⟨ha, hts.trans <| Set.inter_subset_left _ _⟩
+    G.CliqueFreeOn (s ∩ G.neighborSet a) n := by classical
 #align simple_graph.clique_free_on.of_succ SimpleGraph.CliqueFreeOn.of_succ
 -/
 
@@ -568,13 +550,7 @@ theorem cliqueSet_map (hn : n ≠ 1) (G : SimpleGraph α) (f : α ↪ β) :
   ext s
   constructor
   · rintro ⟨hs, rfl⟩
-    have hs' : (s.preimage f <| f.injective.inj_on _).map f = s := by
-      classical
-      rw [map_eq_image, image_preimage, filter_true_of_mem]
-      rintro a ha
-      obtain ⟨b, hb, hba⟩ := exists_mem_ne (hn.lt_of_le' <| Finset.card_pos.2 ⟨a, ha⟩) a
-      obtain ⟨c, _, _, hc, _⟩ := hs ha hb hba.symm
-      exact ⟨c, hc⟩
+    have hs' : (s.preimage f <| f.injective.inj_on _).map f = s := by classical
     refine' ⟨s.preimage f <| f.injective.inj_on _, ⟨_, by rw [← card_map f, hs']⟩, hs'⟩
     rw [coe_preimage]
     exact fun a ha b hb hab => map_adj_apply.1 (hs ha hb <| f.injective.ne hab)

bump to nightly-2023-12-16-06

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

4e55c28d

Diff

@@ -80,34 +80,46 @@ instance [DecidableEq α] [DecidableRel G.Adj] {s : Finset α} : Decidable (G.Is
 
 variable {G H} {a b : α}
 
+#print SimpleGraph.isClique_empty /-
 @[simp]
 theorem isClique_empty : G.IsClique ∅ :=
   Set.pairwise_empty _
 #align simple_graph.is_clique_empty SimpleGraph.isClique_empty
+-/
 
+#print SimpleGraph.isClique_singleton /-
 @[simp]
 theorem isClique_singleton (a : α) : G.IsClique {a} :=
   Set.pairwise_singleton _ _
 #align simple_graph.is_clique_singleton SimpleGraph.isClique_singleton
+-/
 
+#print SimpleGraph.isClique_pair /-
 theorem isClique_pair : G.IsClique {a, b} ↔ a ≠ b → G.Adj a b :=
   Set.pairwise_pair_of_symmetric G.symm
 #align simple_graph.is_clique_pair SimpleGraph.isClique_pair
+-/
 
+#print SimpleGraph.isClique_insert /-
 @[simp]
 theorem isClique_insert : G.IsClique (insert a s) ↔ G.IsClique s ∧ ∀ b ∈ s, a ≠ b → G.Adj a b :=
   Set.pairwise_insert_of_symmetric G.symm
 #align simple_graph.is_clique_insert SimpleGraph.isClique_insert
+-/
 
+#print SimpleGraph.isClique_insert_of_not_mem /-
 theorem isClique_insert_of_not_mem (ha : a ∉ s) :
     G.IsClique (insert a s) ↔ G.IsClique s ∧ ∀ b ∈ s, G.Adj a b :=
   Set.pairwise_insert_of_symmetric_of_not_mem G.symm ha
 #align simple_graph.is_clique_insert_of_not_mem SimpleGraph.isClique_insert_of_not_mem
+-/
 
+#print SimpleGraph.IsClique.insert /-
 theorem IsClique.insert (hs : G.IsClique s) (h : ∀ b ∈ s, a ≠ b → G.Adj a b) :
     G.IsClique (insert a s) :=
   hs.insert_of_symmetric G.symm h
 #align simple_graph.is_clique.insert SimpleGraph.IsClique.insert
+-/
 
 #print SimpleGraph.IsClique.mono /-
 theorem IsClique.mono (h : G ≤ H) : G.IsClique s → H.IsClique s :=
@@ -121,12 +133,14 @@ theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t :=
 #align simple_graph.is_clique.subset SimpleGraph.IsClique.subset
 -/
 
+#print SimpleGraph.IsClique.map /-
 protected theorem IsClique.map {G : SimpleGraph α} {s : Set α} (h : G.IsClique s) {f : α ↪ β} :
     (G.map f).IsClique (f '' s) :=
   by
   rintro _ ⟨a, ha, rfl⟩ _ ⟨b, hb, rfl⟩ hab
   exact ⟨a, b, h ha hb <| ne_of_apply_ne _ hab, rfl, rfl⟩
 #align simple_graph.is_clique.map SimpleGraph.IsClique.map
+-/
 
 #print SimpleGraph.isClique_bot_iff /-
 @[simp]
@@ -167,13 +181,17 @@ instance [DecidableEq α] [DecidableRel G.Adj] {n : ℕ} {s : Finset α} :
 
 variable {G H} {a b c : α}
 
+#print SimpleGraph.isNClique_empty /-
 @[simp]
 theorem isNClique_empty : G.IsNClique n ∅ ↔ n = 0 := by simp [is_n_clique_iff, eq_comm]
 #align simple_graph.is_n_clique_empty SimpleGraph.isNClique_empty
+-/
 
+#print SimpleGraph.isNClique_singleton /-
 @[simp]
 theorem isNClique_singleton : G.IsNClique n {a} ↔ n = 1 := by simp [is_n_clique_iff, eq_comm]
 #align simple_graph.is_n_clique_singleton SimpleGraph.isNClique_singleton
+-/
 
 #print SimpleGraph.IsNClique.mono /-
 theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s := by
@@ -181,10 +199,12 @@ theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s := by
 #align simple_graph.is_n_clique.mono SimpleGraph.IsNClique.mono
 -/
 
+#print SimpleGraph.IsNClique.map /-
 protected theorem IsNClique.map (h : G.IsNClique n s) {f : α ↪ β} :
     (G.map f).IsNClique n (s.map f) :=
   ⟨by rw [coe_map]; exact h.1.map, (card_map _).trans h.2⟩
 #align simple_graph.is_n_clique.map SimpleGraph.IsNClique.map
+-/
 
 #print SimpleGraph.isNClique_bot_iff /-
 @[simp]
@@ -197,18 +217,23 @@ theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧
 #align simple_graph.is_n_clique_bot_iff SimpleGraph.isNClique_bot_iff
 -/
 
+#print SimpleGraph.isNClique_zero /-
 @[simp]
 theorem isNClique_zero : G.IsNClique 0 s ↔ s = ∅ := by
   simp only [is_n_clique_iff, Finset.card_eq_zero, and_iff_right_iff_imp]; rintro rfl; simp
 #align simple_graph.is_n_clique_zero SimpleGraph.isNClique_zero
+-/
 
+#print SimpleGraph.isNClique_one /-
 @[simp]
 theorem isNClique_one : G.IsNClique 1 s ↔ ∃ a, s = {a} := by
   simp only [is_n_clique_iff, card_eq_one, and_iff_right_iff_imp]; rintro ⟨a, rfl⟩; simp
 #align simple_graph.is_n_clique_one SimpleGraph.isNClique_one
+-/
 
 variable [DecidableEq α]
 
+#print SimpleGraph.IsNClique.insert /-
 theorem IsNClique.insert (hs : G.IsNClique n s) (h : ∀ b ∈ s, G.Adj a b) :
     G.IsNClique (n + 1) (insert a s) := by
   constructor
@@ -216,6 +241,7 @@ theorem IsNClique.insert (hs : G.IsNClique n s) (h : ∀ b ∈ s, G.Adj a b) :
     exact hs.1.insert fun b hb _ => h _ hb
   · rw [card_insert_of_not_mem fun ha => (h _ ha).Ne rfl, hs.2]
 #align simple_graph.is_n_clique.insert SimpleGraph.IsNClique.insert
+-/
 
 #print SimpleGraph.is3Clique_triple_iff /-
 theorem is3Clique_triple_iff : G.IsNClique 3 {a, b, c} ↔ G.Adj a b ∧ G.Adj a c ∧ G.Adj b c :=
@@ -360,6 +386,7 @@ theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :
 #align simple_graph.clique_free_of_card_lt SimpleGraph.cliqueFree_of_card_lt
 -/
 
+#print SimpleGraph.cliqueFree_two /-
 @[simp]
 theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
   classical
@@ -369,6 +396,7 @@ theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
   · rintro rfl
     exact clique_free_bot le_rfl
 #align simple_graph.clique_free_two SimpleGraph.cliqueFree_two
+-/
 
 end CliqueFree
 
@@ -376,49 +404,68 @@ section CliqueFreeOn
 
 variable {s s₁ s₂ : Set α} {t : Finset α} {a b : α} {m n : ℕ}
 
+#print SimpleGraph.CliqueFreeOn /-
 /-- `G.clique_free_on s n` means that `G` has no `n`-cliques contained in `s`. -/
 def CliqueFreeOn (G : SimpleGraph α) (s : Set α) (n : ℕ) : Prop :=
   ∀ ⦃t⦄, ↑t ⊆ s → ¬G.IsNClique n t
 #align simple_graph.clique_free_on SimpleGraph.CliqueFreeOn
+-/
 
+#print SimpleGraph.CliqueFreeOn.subset /-
 theorem CliqueFreeOn.subset (hs : s₁ ⊆ s₂) (h₂ : G.CliqueFreeOn s₂ n) : G.CliqueFreeOn s₁ n :=
   fun t hts => h₂ <| hts.trans hs
 #align simple_graph.clique_free_on.subset SimpleGraph.CliqueFreeOn.subset
+-/
 
+#print SimpleGraph.CliqueFreeOn.mono /-
 theorem CliqueFreeOn.mono (hmn : m ≤ n) (hG : G.CliqueFreeOn s m) : G.CliqueFreeOn s n :=
   by
   rintro t hts ht
   obtain ⟨u, hut, hu⟩ := t.exists_smaller_set _ (hmn.trans ht.card_eq.ge)
   exact hG ((coe_subset.2 hut).trans hts) ⟨ht.clique.subset hut, hu⟩
 #align simple_graph.clique_free_on.mono SimpleGraph.CliqueFreeOn.mono
+-/
 
+#print SimpleGraph.CliqueFreeOn.anti /-
 theorem CliqueFreeOn.anti (hGH : G ≤ H) (hH : H.CliqueFreeOn s n) : G.CliqueFreeOn s n :=
   fun t hts ht => hH hts <| ht.mono hGH
 #align simple_graph.clique_free_on.anti SimpleGraph.CliqueFreeOn.anti
+-/
 
+#print SimpleGraph.cliqueFreeOn_empty /-
 @[simp]
 theorem cliqueFreeOn_empty : G.CliqueFreeOn ∅ n ↔ n ≠ 0 := by
   simp [clique_free_on, Set.subset_empty_iff]
 #align simple_graph.clique_free_on_empty SimpleGraph.cliqueFreeOn_empty
+-/
 
+#print SimpleGraph.cliqueFreeOn_singleton /-
 @[simp]
 theorem cliqueFreeOn_singleton : G.CliqueFreeOn {a} n ↔ 1 < n := by
   obtain _ | _ | n := n <;> simp [clique_free_on, Set.subset_singleton_iff_eq]
 #align simple_graph.clique_free_on_singleton SimpleGraph.cliqueFreeOn_singleton
+-/
 
+#print SimpleGraph.cliqueFreeOn_univ /-
 @[simp]
 theorem cliqueFreeOn_univ : G.CliqueFreeOn Set.univ n ↔ G.CliqueFree n := by
   simp [clique_free, clique_free_on]
 #align simple_graph.clique_free_on_univ SimpleGraph.cliqueFreeOn_univ
+-/
 
+#print SimpleGraph.CliqueFree.cliqueFreeOn /-
 protected theorem CliqueFree.cliqueFreeOn (hG : G.CliqueFree n) : G.CliqueFreeOn s n := fun t _ =>
   hG _
 #align simple_graph.clique_free.clique_free_on SimpleGraph.CliqueFree.cliqueFreeOn
+-/
 
+#print SimpleGraph.cliqueFreeOn_of_card_lt /-
 theorem cliqueFreeOn_of_card_lt {s : Finset α} (h : s.card < n) : G.CliqueFreeOn s n :=
   fun t hts ht => h.not_le <| ht.2.symm.trans_le <| card_mono hts
 #align simple_graph.clique_free_on_of_card_lt SimpleGraph.cliqueFreeOn_of_card_lt
+-/
 
+#print SimpleGraph.cliqueFreeOn_two /-
 --TOOD: Restate using `simple_graph.indep_set` once we have it
 @[simp]
 theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by
@@ -431,7 +478,9 @@ theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by
   simp only [coe_insert, coe_singleton, Set.insert_subset_iff, Set.singleton_subset_iff] at hst 
   refine' h hst.1 hst.2 hab (ht _ _ hab) <;> simp
 #align simple_graph.clique_free_on_two SimpleGraph.cliqueFreeOn_two
+-/
 
+#print SimpleGraph.CliqueFreeOn.of_succ /-
 theorem CliqueFreeOn.of_succ (hs : G.CliqueFreeOn s (n + 1)) (ha : a ∈ s) :
     G.CliqueFreeOn (s ∩ G.neighborSet a) n := by
   classical
@@ -439,6 +488,7 @@ theorem CliqueFreeOn.of_succ (hs : G.CliqueFreeOn s (n + 1)) (ha : a ∈ s) :
   push_cast
   exact Set.insert_subset_iff.2 ⟨ha, hts.trans <| Set.inter_subset_left _ _⟩
 #align simple_graph.clique_free_on.of_succ SimpleGraph.CliqueFreeOn.of_succ
+-/
 
 end CliqueFreeOn
 
@@ -489,21 +539,28 @@ theorem cliqueSet_mono' (h : G ≤ H) : G.cliqueSet ≤ H.cliqueSet := fun _ =>
 #align simple_graph.clique_set_mono' SimpleGraph.cliqueSet_mono'
 -/
 
+#print SimpleGraph.cliqueSet_zero /-
 @[simp]
 theorem cliqueSet_zero (G : SimpleGraph α) : G.cliqueSet 0 = {∅} :=
   Set.ext fun s => by simp
 #align simple_graph.clique_set_zero SimpleGraph.cliqueSet_zero
+-/
 
+#print SimpleGraph.cliqueSet_one /-
 @[simp]
 theorem cliqueSet_one (G : SimpleGraph α) : G.cliqueSet 1 = Set.range singleton :=
   Set.ext fun s => by simp [eq_comm]
 #align simple_graph.clique_set_one SimpleGraph.cliqueSet_one
+-/
 
+#print SimpleGraph.cliqueSet_bot /-
 @[simp]
 theorem cliqueSet_bot (hn : 1 < n) : (⊥ : SimpleGraph α).cliqueSet n = ∅ :=
   (cliqueFree_bot hn).cliqueSet
 #align simple_graph.clique_set_bot SimpleGraph.cliqueSet_bot
+-/
 
+#print SimpleGraph.cliqueSet_map /-
 @[simp]
 theorem cliqueSet_map (hn : n ≠ 1) (G : SimpleGraph α) (f : α ↪ β) :
     (G.map f).cliqueSet n = map f '' G.cliqueSet n :=
@@ -524,7 +581,9 @@ theorem cliqueSet_map (hn : n ≠ 1) (G : SimpleGraph α) (f : α ↪ β) :
   · rintro ⟨s, hs, rfl⟩
     exact is_n_clique.map hs
 #align simple_graph.clique_set_map SimpleGraph.cliqueSet_map
+-/
 
+#print SimpleGraph.cliqueSet_map_of_equiv /-
 @[simp]
 theorem cliqueSet_map_of_equiv (G : SimpleGraph α) (e : α ≃ β) (n : ℕ) :
     (G.map e.toEmbedding).cliqueSet n = map e.toEmbedding '' G.cliqueSet n :=
@@ -534,6 +593,7 @@ theorem cliqueSet_map_of_equiv (G : SimpleGraph α) (e : α ≃ β) (n : ℕ) :
     simp [e.exists_congr_left]
   · exact clique_set_map hn _ _
 #align simple_graph.clique_set_map_of_equiv SimpleGraph.cliqueSet_map_of_equiv
+-/
 
 end CliqueSet
 
@@ -579,12 +639,14 @@ attribute [protected] clique_free.clique_finset
 
 variable {G}
 
+#print SimpleGraph.card_cliqueFinset_le /-
 theorem card_cliqueFinset_le : (G.cliqueFinset n).card ≤ (card α).choose n :=
   by
   rw [← card_univ, ← card_powerset_len]
   refine' card_mono fun s => _
   simpa [mem_powerset_len_univ_iff] using is_n_clique.card_eq
 #align simple_graph.card_clique_finset_le SimpleGraph.card_cliqueFinset_le
+-/
 
 variable [DecidableRel H.Adj]
 
@@ -597,19 +659,23 @@ theorem cliqueFinset_mono (h : G ≤ H) : G.cliqueFinset n ⊆ H.cliqueFinset n
 
 variable [Fintype β] [DecidableEq β] (G)
 
+#print SimpleGraph.cliqueFinset_map /-
 @[simp]
 theorem cliqueFinset_map (f : α ↪ β) (hn : n ≠ 1) :
     (G.map f).cliqueFinset n = (G.cliqueFinset n).map ⟨map f, Finset.map_injective _⟩ :=
   coe_injective <| by
     simp_rw [coe_clique_finset, clique_set_map hn, coe_map, coe_clique_finset, embedding.coe_fn_mk]
 #align simple_graph.clique_finset_map SimpleGraph.cliqueFinset_map
+-/
 
+#print SimpleGraph.cliqueFinset_map_of_equiv /-
 @[simp]
 theorem cliqueFinset_map_of_equiv (e : α ≃ β) (n : ℕ) :
     (G.map e.toEmbedding).cliqueFinset n =
       (G.cliqueFinset n).map ⟨map e.toEmbedding, Finset.map_injective _⟩ :=
   coe_injective <| by push_cast <;> exact clique_set_map_of_equiv _ _ _
 #align simple_graph.clique_finset_map_of_equiv SimpleGraph.cliqueFinset_map_of_equiv
+-/
 
 end CliqueFinset

bump to nightly-2023-11-06-06

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

f9f7c90b

Diff

@@ -354,7 +354,7 @@ theorem CliqueFree.anti (h : G ≤ H) : H.CliqueFree n → G.CliqueFree n :=
 theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :=
   by
   by_contra h
-  refine' Nat.lt_le_antisymm hc _
+  refine' Nat.lt_le_asymm hc _
   rw [clique_free_iff, not_isEmpty_iff] at h 
   simpa using Fintype.card_le_of_embedding h.some.to_embedding
 #align simple_graph.clique_free_of_card_lt SimpleGraph.cliqueFree_of_card_lt

bump to nightly-2023-10-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe

5b21425a

Diff

@@ -5,8 +5,9 @@ Authors: Yaël Dillies, Bhavik Mehta
 -/
 import Combinatorics.SimpleGraph.Basic
 import Data.Finset.Pairwise
+import Data.Finset.Preimage
 
-#align_import combinatorics.simple_graph.clique from "leanprover-community/mathlib"@"ee05e9ce1322178f0c12004eb93c00d2c8c00ed2"
+#align_import combinatorics.simple_graph.clique from "leanprover-community/mathlib"@"3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe"
 
 /-!
 # Graph cliques
@@ -27,15 +28,15 @@ adjacent.
 ## TODO
 
 * Clique numbers
-* Do we need `clique_set`, a version of `clique_finset` for infinite graphs?
+* Dualise all the API to get independent sets
 -/
 
 
-open Finset Fintype
+open Finset Fintype Function
 
 namespace SimpleGraph
 
-variable {α : Type _} (G H : SimpleGraph α)
+variable {α β : Type _} (G H : SimpleGraph α)
 
 /-! ### Cliques -/
 
@@ -77,20 +78,56 @@ theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ :=
 instance [DecidableEq α] [DecidableRel G.Adj] {s : Finset α} : Decidable (G.IsClique s) :=
   decidable_of_iff' _ G.isClique_iff
 
-variable {G H}
+variable {G H} {a b : α}
+
+@[simp]
+theorem isClique_empty : G.IsClique ∅ :=
+  Set.pairwise_empty _
+#align simple_graph.is_clique_empty SimpleGraph.isClique_empty
+
+@[simp]
+theorem isClique_singleton (a : α) : G.IsClique {a} :=
+  Set.pairwise_singleton _ _
+#align simple_graph.is_clique_singleton SimpleGraph.isClique_singleton
+
+theorem isClique_pair : G.IsClique {a, b} ↔ a ≠ b → G.Adj a b :=
+  Set.pairwise_pair_of_symmetric G.symm
+#align simple_graph.is_clique_pair SimpleGraph.isClique_pair
+
+@[simp]
+theorem isClique_insert : G.IsClique (insert a s) ↔ G.IsClique s ∧ ∀ b ∈ s, a ≠ b → G.Adj a b :=
+  Set.pairwise_insert_of_symmetric G.symm
+#align simple_graph.is_clique_insert SimpleGraph.isClique_insert
+
+theorem isClique_insert_of_not_mem (ha : a ∉ s) :
+    G.IsClique (insert a s) ↔ G.IsClique s ∧ ∀ b ∈ s, G.Adj a b :=
+  Set.pairwise_insert_of_symmetric_of_not_mem G.symm ha
+#align simple_graph.is_clique_insert_of_not_mem SimpleGraph.isClique_insert_of_not_mem
+
+theorem IsClique.insert (hs : G.IsClique s) (h : ∀ b ∈ s, a ≠ b → G.Adj a b) :
+    G.IsClique (insert a s) :=
+  hs.insert_of_symmetric G.symm h
+#align simple_graph.is_clique.insert SimpleGraph.IsClique.insert
 
 #print SimpleGraph.IsClique.mono /-
-theorem IsClique.mono (h : G ≤ H) : G.IsClique s → H.IsClique s := by simp_rw [is_clique_iff];
-  exact Set.Pairwise.mono' h
+theorem IsClique.mono (h : G ≤ H) : G.IsClique s → H.IsClique s :=
+  Set.Pairwise.mono' h
 #align simple_graph.is_clique.mono SimpleGraph.IsClique.mono
 -/
 
 #print SimpleGraph.IsClique.subset /-
-theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t := by simp_rw [is_clique_iff];
-  exact Set.Pairwise.mono h
+theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t :=
+  Set.Pairwise.mono h
 #align simple_graph.is_clique.subset SimpleGraph.IsClique.subset
 -/
 
+protected theorem IsClique.map {G : SimpleGraph α} {s : Set α} (h : G.IsClique s) {f : α ↪ β} :
+    (G.map f).IsClique (f '' s) :=
+  by
+  rintro _ ⟨a, ha, rfl⟩ _ ⟨b, hb, rfl⟩ hab
+  exact ⟨a, b, h ha hb <| ne_of_apply_ne _ hab, rfl, rfl⟩
+#align simple_graph.is_clique.map SimpleGraph.IsClique.map
+
 #print SimpleGraph.isClique_bot_iff /-
 @[simp]
 theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Subsingleton :=
@@ -128,7 +165,15 @@ instance [DecidableEq α] [DecidableRel G.Adj] {n : ℕ} {s : Finset α} :
     Decidable (G.IsNClique n s) :=
   decidable_of_iff' _ G.isNClique_iff
 
-variable {G H}
+variable {G H} {a b c : α}
+
+@[simp]
+theorem isNClique_empty : G.IsNClique n ∅ ↔ n = 0 := by simp [is_n_clique_iff, eq_comm]
+#align simple_graph.is_n_clique_empty SimpleGraph.isNClique_empty
+
+@[simp]
+theorem isNClique_singleton : G.IsNClique n {a} ↔ n = 1 := by simp [is_n_clique_iff, eq_comm]
+#align simple_graph.is_n_clique_singleton SimpleGraph.isNClique_singleton
 
 #print SimpleGraph.IsNClique.mono /-
 theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s := by
@@ -136,6 +181,11 @@ theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s := by
 #align simple_graph.is_n_clique.mono SimpleGraph.IsNClique.mono
 -/
 
+protected theorem IsNClique.map (h : G.IsNClique n s) {f : α ↪ β} :
+    (G.map f).IsNClique n (s.map f) :=
+  ⟨by rw [coe_map]; exact h.1.map, (card_map _).trans h.2⟩
+#align simple_graph.is_n_clique.map SimpleGraph.IsNClique.map
+
 #print SimpleGraph.isNClique_bot_iff /-
 @[simp]
 theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧ s.card = n :=
@@ -147,7 +197,25 @@ theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧
 #align simple_graph.is_n_clique_bot_iff SimpleGraph.isNClique_bot_iff
 -/
 
-variable [DecidableEq α] {a b c : α}
+@[simp]
+theorem isNClique_zero : G.IsNClique 0 s ↔ s = ∅ := by
+  simp only [is_n_clique_iff, Finset.card_eq_zero, and_iff_right_iff_imp]; rintro rfl; simp
+#align simple_graph.is_n_clique_zero SimpleGraph.isNClique_zero
+
+@[simp]
+theorem isNClique_one : G.IsNClique 1 s ↔ ∃ a, s = {a} := by
+  simp only [is_n_clique_iff, card_eq_one, and_iff_right_iff_imp]; rintro ⟨a, rfl⟩; simp
+#align simple_graph.is_n_clique_one SimpleGraph.isNClique_one
+
+variable [DecidableEq α]
+
+theorem IsNClique.insert (hs : G.IsNClique n s) (h : ∀ b ∈ s, G.Adj a b) :
+    G.IsNClique (n + 1) (insert a s) := by
+  constructor
+  · push_cast
+    exact hs.1.insert fun b hb _ => h _ hb
+  · rw [card_insert_of_not_mem fun ha => (h _ ha).Ne rfl, hs.2]
+#align simple_graph.is_n_clique.insert SimpleGraph.IsNClique.insert
 
 #print SimpleGraph.is3Clique_triple_iff /-
 theorem is3Clique_triple_iff : G.IsNClique 3 {a, b, c} ↔ G.Adj a b ∧ G.Adj a c ∧ G.Adj b c :=
@@ -257,6 +325,7 @@ theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGrap
 -/
 
 #print SimpleGraph.cliqueFree_bot /-
+@[simp]
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n :=
   by
   rintro t ht
@@ -291,8 +360,88 @@ theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :
 #align simple_graph.clique_free_of_card_lt SimpleGraph.cliqueFree_of_card_lt
 -/
 
+@[simp]
+theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
+  classical
+  constructor
+  · simp_rw [← edge_set_eq_empty, Set.eq_empty_iff_forall_not_mem, Sym2.forall, mem_edge_set]
+    exact fun h a b hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.Ne⟩
+  · rintro rfl
+    exact clique_free_bot le_rfl
+#align simple_graph.clique_free_two SimpleGraph.cliqueFree_two
+
 end CliqueFree
 
+section CliqueFreeOn
+
+variable {s s₁ s₂ : Set α} {t : Finset α} {a b : α} {m n : ℕ}
+
+/-- `G.clique_free_on s n` means that `G` has no `n`-cliques contained in `s`. -/
+def CliqueFreeOn (G : SimpleGraph α) (s : Set α) (n : ℕ) : Prop :=
+  ∀ ⦃t⦄, ↑t ⊆ s → ¬G.IsNClique n t
+#align simple_graph.clique_free_on SimpleGraph.CliqueFreeOn
+
+theorem CliqueFreeOn.subset (hs : s₁ ⊆ s₂) (h₂ : G.CliqueFreeOn s₂ n) : G.CliqueFreeOn s₁ n :=
+  fun t hts => h₂ <| hts.trans hs
+#align simple_graph.clique_free_on.subset SimpleGraph.CliqueFreeOn.subset
+
+theorem CliqueFreeOn.mono (hmn : m ≤ n) (hG : G.CliqueFreeOn s m) : G.CliqueFreeOn s n :=
+  by
+  rintro t hts ht
+  obtain ⟨u, hut, hu⟩ := t.exists_smaller_set _ (hmn.trans ht.card_eq.ge)
+  exact hG ((coe_subset.2 hut).trans hts) ⟨ht.clique.subset hut, hu⟩
+#align simple_graph.clique_free_on.mono SimpleGraph.CliqueFreeOn.mono
+
+theorem CliqueFreeOn.anti (hGH : G ≤ H) (hH : H.CliqueFreeOn s n) : G.CliqueFreeOn s n :=
+  fun t hts ht => hH hts <| ht.mono hGH
+#align simple_graph.clique_free_on.anti SimpleGraph.CliqueFreeOn.anti
+
+@[simp]
+theorem cliqueFreeOn_empty : G.CliqueFreeOn ∅ n ↔ n ≠ 0 := by
+  simp [clique_free_on, Set.subset_empty_iff]
+#align simple_graph.clique_free_on_empty SimpleGraph.cliqueFreeOn_empty
+
+@[simp]
+theorem cliqueFreeOn_singleton : G.CliqueFreeOn {a} n ↔ 1 < n := by
+  obtain _ | _ | n := n <;> simp [clique_free_on, Set.subset_singleton_iff_eq]
+#align simple_graph.clique_free_on_singleton SimpleGraph.cliqueFreeOn_singleton
+
+@[simp]
+theorem cliqueFreeOn_univ : G.CliqueFreeOn Set.univ n ↔ G.CliqueFree n := by
+  simp [clique_free, clique_free_on]
+#align simple_graph.clique_free_on_univ SimpleGraph.cliqueFreeOn_univ
+
+protected theorem CliqueFree.cliqueFreeOn (hG : G.CliqueFree n) : G.CliqueFreeOn s n := fun t _ =>
+  hG _
+#align simple_graph.clique_free.clique_free_on SimpleGraph.CliqueFree.cliqueFreeOn
+
+theorem cliqueFreeOn_of_card_lt {s : Finset α} (h : s.card < n) : G.CliqueFreeOn s n :=
+  fun t hts ht => h.not_le <| ht.2.symm.trans_le <| card_mono hts
+#align simple_graph.clique_free_on_of_card_lt SimpleGraph.cliqueFreeOn_of_card_lt
+
+--TOOD: Restate using `simple_graph.indep_set` once we have it
+@[simp]
+theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by
+  classical
+  refine' ⟨fun h a ha b hb _ hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.Ne⟩, _⟩
+  · push_cast
+    exact Set.insert_subset_iff.2 ⟨ha, Set.singleton_subset_iff.2 hb⟩
+  simp only [clique_free_on, is_n_clique_iff, card_eq_two, coe_subset, not_and, not_exists]
+  rintro h t hst ht a b hab rfl
+  simp only [coe_insert, coe_singleton, Set.insert_subset_iff, Set.singleton_subset_iff] at hst 
+  refine' h hst.1 hst.2 hab (ht _ _ hab) <;> simp
+#align simple_graph.clique_free_on_two SimpleGraph.cliqueFreeOn_two
+
+theorem CliqueFreeOn.of_succ (hs : G.CliqueFreeOn s (n + 1)) (ha : a ∈ s) :
+    G.CliqueFreeOn (s ∩ G.neighborSet a) n := by
+  classical
+  refine' fun t hts ht => hs _ (ht.insert fun b hb => (hts hb).2)
+  push_cast
+  exact Set.insert_subset_iff.2 ⟨ha, hts.trans <| Set.inter_subset_left _ _⟩
+#align simple_graph.clique_free_on.of_succ SimpleGraph.CliqueFreeOn.of_succ
+
+end CliqueFreeOn
+
 /-! ### Set of cliques -/
 
 
@@ -308,6 +457,7 @@ def cliqueSet (n : ℕ) : Set (Finset α) :=
 -/
 
 #print SimpleGraph.mem_cliqueSet_iff /-
+@[simp]
 theorem mem_cliqueSet_iff : s ∈ G.cliqueSet n ↔ G.IsNClique n s :=
   Iff.rfl
 #align simple_graph.mem_clique_set_iff SimpleGraph.mem_cliqueSet_iff
@@ -320,13 +470,14 @@ theorem cliqueSet_eq_empty_iff : G.cliqueSet n = ∅ ↔ G.CliqueFree n := by
 #align simple_graph.clique_set_eq_empty_iff SimpleGraph.cliqueSet_eq_empty_iff
 -/
 
-alias ⟨_, clique_free.clique_set⟩ := clique_set_eq_empty_iff
-#align simple_graph.clique_free.clique_set SimpleGraph.CliqueFree.cliqueSet
-
-attribute [protected] clique_free.clique_set
-
 variable {G H}
 
+#print SimpleGraph.CliqueFree.cliqueSet /-
+protected theorem CliqueFree.cliqueSet : G.CliqueFree n → G.cliqueSet n = ∅ :=
+  G.cliqueSet_eq_empty_iff.2
+#align simple_graph.clique_free.clique_set SimpleGraph.CliqueFree.cliqueSet
+-/
+
 #print SimpleGraph.cliqueSet_mono /-
 @[mono]
 theorem cliqueSet_mono (h : G ≤ H) : G.cliqueSet n ⊆ H.cliqueSet n := fun _ => IsNClique.mono h
@@ -338,6 +489,52 @@ theorem cliqueSet_mono' (h : G ≤ H) : G.cliqueSet ≤ H.cliqueSet := fun _ =>
 #align simple_graph.clique_set_mono' SimpleGraph.cliqueSet_mono'
 -/
 
+@[simp]
+theorem cliqueSet_zero (G : SimpleGraph α) : G.cliqueSet 0 = {∅} :=
+  Set.ext fun s => by simp
+#align simple_graph.clique_set_zero SimpleGraph.cliqueSet_zero
+
+@[simp]
+theorem cliqueSet_one (G : SimpleGraph α) : G.cliqueSet 1 = Set.range singleton :=
+  Set.ext fun s => by simp [eq_comm]
+#align simple_graph.clique_set_one SimpleGraph.cliqueSet_one
+
+@[simp]
+theorem cliqueSet_bot (hn : 1 < n) : (⊥ : SimpleGraph α).cliqueSet n = ∅ :=
+  (cliqueFree_bot hn).cliqueSet
+#align simple_graph.clique_set_bot SimpleGraph.cliqueSet_bot
+
+@[simp]
+theorem cliqueSet_map (hn : n ≠ 1) (G : SimpleGraph α) (f : α ↪ β) :
+    (G.map f).cliqueSet n = map f '' G.cliqueSet n :=
+  by
+  ext s
+  constructor
+  · rintro ⟨hs, rfl⟩
+    have hs' : (s.preimage f <| f.injective.inj_on _).map f = s := by
+      classical
+      rw [map_eq_image, image_preimage, filter_true_of_mem]
+      rintro a ha
+      obtain ⟨b, hb, hba⟩ := exists_mem_ne (hn.lt_of_le' <| Finset.card_pos.2 ⟨a, ha⟩) a
+      obtain ⟨c, _, _, hc, _⟩ := hs ha hb hba.symm
+      exact ⟨c, hc⟩
+    refine' ⟨s.preimage f <| f.injective.inj_on _, ⟨_, by rw [← card_map f, hs']⟩, hs'⟩
+    rw [coe_preimage]
+    exact fun a ha b hb hab => map_adj_apply.1 (hs ha hb <| f.injective.ne hab)
+  · rintro ⟨s, hs, rfl⟩
+    exact is_n_clique.map hs
+#align simple_graph.clique_set_map SimpleGraph.cliqueSet_map
+
+@[simp]
+theorem cliqueSet_map_of_equiv (G : SimpleGraph α) (e : α ≃ β) (n : ℕ) :
+    (G.map e.toEmbedding).cliqueSet n = map e.toEmbedding '' G.cliqueSet n :=
+  by
+  obtain rfl | hn := eq_or_ne n 1
+  · ext
+    simp [e.exists_congr_left]
+  · exact clique_set_map hn _ _
+#align simple_graph.clique_set_map_of_equiv SimpleGraph.cliqueSet_map_of_equiv
+
 end CliqueSet
 
 /-! ### Finset of cliques -/
@@ -355,13 +552,14 @@ def cliqueFinset (n : ℕ) : Finset (Finset α) :=
 -/
 
 #print SimpleGraph.mem_cliqueFinset_iff /-
+@[simp]
 theorem mem_cliqueFinset_iff : s ∈ G.cliqueFinset n ↔ G.IsNClique n s :=
   mem_filter.trans <| and_iff_right <| mem_univ _
 #align simple_graph.mem_clique_finset_iff SimpleGraph.mem_cliqueFinset_iff
 -/
 
 #print SimpleGraph.coe_cliqueFinset /-
-@[simp]
+@[simp, norm_cast]
 theorem coe_cliqueFinset (n : ℕ) : (G.cliqueFinset n : Set (Finset α)) = G.cliqueSet n :=
   Set.ext fun _ => mem_cliqueFinset_iff _
 #align simple_graph.coe_clique_finset SimpleGraph.coe_cliqueFinset
@@ -379,7 +577,16 @@ alias ⟨_, _root_.simple_graph.clique_free.clique_finset⟩ := clique_finset_eq
 
 attribute [protected] clique_free.clique_finset
 
-variable {G} [DecidableRel H.Adj]
+variable {G}
+
+theorem card_cliqueFinset_le : (G.cliqueFinset n).card ≤ (card α).choose n :=
+  by
+  rw [← card_univ, ← card_powerset_len]
+  refine' card_mono fun s => _
+  simpa [mem_powerset_len_univ_iff] using is_n_clique.card_eq
+#align simple_graph.card_clique_finset_le SimpleGraph.card_cliqueFinset_le
+
+variable [DecidableRel H.Adj]
 
 #print SimpleGraph.cliqueFinset_mono /-
 @[mono]
@@ -388,6 +595,22 @@ theorem cliqueFinset_mono (h : G ≤ H) : G.cliqueFinset n ⊆ H.cliqueFinset n
 #align simple_graph.clique_finset_mono SimpleGraph.cliqueFinset_mono
 -/
 
+variable [Fintype β] [DecidableEq β] (G)
+
+@[simp]
+theorem cliqueFinset_map (f : α ↪ β) (hn : n ≠ 1) :
+    (G.map f).cliqueFinset n = (G.cliqueFinset n).map ⟨map f, Finset.map_injective _⟩ :=
+  coe_injective <| by
+    simp_rw [coe_clique_finset, clique_set_map hn, coe_map, coe_clique_finset, embedding.coe_fn_mk]
+#align simple_graph.clique_finset_map SimpleGraph.cliqueFinset_map
+
+@[simp]
+theorem cliqueFinset_map_of_equiv (e : α ≃ β) (n : ℕ) :
+    (G.map e.toEmbedding).cliqueFinset n =
+      (G.cliqueFinset n).map ⟨map e.toEmbedding, Finset.map_injective _⟩ :=
+  coe_injective <| by push_cast <;> exact clique_set_map_of_equiv _ _ _
+#align simple_graph.clique_finset_map_of_equiv SimpleGraph.cliqueFinset_map_of_equiv
+
 end CliqueFinset
 
 end SimpleGraph

bump to nightly-2023-10-21-06

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

a2dc86f8

Diff

@@ -200,7 +200,8 @@ theorem IsNClique.not_cliqueFree (hG : G.IsNClique n s) : ¬G.CliqueFree n := fu
 theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n)) ↪g G) :
     ¬G.CliqueFree n :=
   by
-  simp only [clique_free, is_n_clique_iff, is_clique_iff_induce_eq, not_forall, Classical.not_not]
+  simp only [clique_free, is_n_clique_iff, is_clique_iff_induce_eq, Classical.not_forall,
+    Classical.not_not]
   use finset.univ.map f.to_embedding
   simp only [card_map, Finset.card_fin, eq_self_iff_true, and_true_iff]
   ext ⟨v, hv⟩ ⟨w, hw⟩
@@ -219,7 +220,7 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
 noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     (⊤ : SimpleGraph (Fin n)) ↪g G :=
   by
-  simp only [clique_free, is_n_clique_iff, is_clique_iff_induce_eq, not_forall,
+  simp only [clique_free, is_n_clique_iff, is_clique_iff_induce_eq, Classical.not_forall,
     Classical.not_not] at h 
   obtain ⟨ha, hb⟩ := h.some_spec
   have : (⊤ : SimpleGraph (Fin h.some.card)) ≃g (⊤ : SimpleGraph h.some) :=

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
 -/
-import Mathbin.Combinatorics.SimpleGraph.Basic
-import Mathbin.Data.Finset.Pairwise
+import Combinatorics.SimpleGraph.Basic
+import Data.Finset.Pairwise
 
 #align_import combinatorics.simple_graph.clique from "leanprover-community/mathlib"@"ee05e9ce1322178f0c12004eb93c00d2c8c00ed2"

bump to nightly-2023-08-23-23

mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504

f612b9e0

Diff

@@ -98,7 +98,7 @@ theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Su
 #align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iff
 -/
 
-alias is_clique_bot_iff ↔ is_clique.subsingleton _
+alias ⟨is_clique.subsingleton, _⟩ := is_clique_bot_iff
 #align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingleton
 
 end Clique
@@ -319,7 +319,7 @@ theorem cliqueSet_eq_empty_iff : G.cliqueSet n = ∅ ↔ G.CliqueFree n := by
 #align simple_graph.clique_set_eq_empty_iff SimpleGraph.cliqueSet_eq_empty_iff
 -/
 
-alias clique_set_eq_empty_iff ↔ _ clique_free.clique_set
+alias ⟨_, clique_free.clique_set⟩ := clique_set_eq_empty_iff
 #align simple_graph.clique_free.clique_set SimpleGraph.CliqueFree.cliqueSet
 
 attribute [protected] clique_free.clique_set
@@ -373,7 +373,7 @@ theorem cliqueFinset_eq_empty_iff : G.cliqueFinset n = ∅ ↔ G.CliqueFree n :=
 #align simple_graph.clique_finset_eq_empty_iff SimpleGraph.cliqueFinset_eq_empty_iff
 -/
 
-alias clique_finset_eq_empty_iff ↔ _ _root_.simple_graph.clique_free.clique_finset
+alias ⟨_, _root_.simple_graph.clique_free.clique_finset⟩ := clique_finset_eq_empty_iff
 #align simple_graph.clique_free.clique_finset SimpleGraph.CliqueFree.cliqueFinset
 
 attribute [protected] clique_free.clique_finset

bump to nightly-2023-08-02-01

mathlib commit https://github.com/leanprover-community/mathlib/commit/63721b2c3eba6c325ecf8ae8cca27155a4f6306f

7aca3f15

Diff

@@ -251,7 +251,7 @@ theorem cliqueFree_iff {n : ℕ} : G.CliqueFree n ↔ IsEmpty ((⊤ : SimpleGrap
 theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGraph α) ↪g G) :
     ¬G.CliqueFree (card α) := by
   rw [not_clique_free_iff]
-  use (iso.complete_graph (Fintype.equivFin α)).symm.toEmbedding.trans f
+  use(iso.complete_graph (Fintype.equivFin α)).symm.toEmbedding.trans f
 #align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embedding
 -/

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.clique
-! 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.Basic
 import Mathbin.Data.Finset.Pairwise
 
+#align_import combinatorics.simple_graph.clique from "leanprover-community/mathlib"@"ee05e9ce1322178f0c12004eb93c00d2c8c00ed2"
+
 /-!
 # Graph cliques

bump to nightly-2023-06-20-01

mathlib commit https://github.com/leanprover-community/mathlib/commit/2a0ce625dbb0ffbc7d1316597de0b25c1ec75303

9b351f8c

Diff

@@ -67,7 +67,7 @@ theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ :=
   rw [is_clique_iff]
   constructor
   · intro h
-    ext (⟨v, hv⟩⟨w, hw⟩)
+    ext ⟨v, hv⟩ ⟨w, hw⟩
     simp only [comap_adj, Subtype.coe_mk, top_adj, Ne.def, Subtype.mk_eq_mk]
     exact ⟨adj.ne, h hv hw⟩
   · intro h v hv w hw hne
@@ -206,7 +206,7 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   simp only [clique_free, is_n_clique_iff, is_clique_iff_induce_eq, not_forall, Classical.not_not]
   use finset.univ.map f.to_embedding
   simp only [card_map, Finset.card_fin, eq_self_iff_true, and_true_iff]
-  ext (⟨v, hv⟩⟨w, hw⟩)
+  ext ⟨v, hv⟩ ⟨w, hw⟩
   simp only [coe_map, RelEmbedding.coe_toEmbedding, Set.mem_image, coe_univ, Set.mem_univ,
     true_and_iff] at hv hw 
   obtain ⟨v', rfl⟩ := hv

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -60,6 +60,7 @@ theorem isClique_iff : G.IsClique s ↔ s.Pairwise G.Adj :=
 #align simple_graph.is_clique_iff SimpleGraph.isClique_iff
 -/
 
+#print SimpleGraph.isClique_iff_induce_eq /-
 /-- A clique is a set of vertices whose induced graph is complete. -/
 theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ :=
   by
@@ -74,6 +75,7 @@ theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ :=
     conv_lhs at this => rw [h]
     simpa [hne]
 #align simple_graph.is_clique_iff_induce_eq SimpleGraph.isClique_iff_induce_eq
+-/
 
 instance [DecidableEq α] [DecidableRel G.Adj] {s : Finset α} : Decidable (G.IsClique s) :=
   decidable_of_iff' _ G.isClique_iff
@@ -92,10 +94,12 @@ theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t := by simp
 #align simple_graph.is_clique.subset SimpleGraph.IsClique.subset
 -/
 
+#print SimpleGraph.isClique_bot_iff /-
 @[simp]
 theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Subsingleton :=
   Set.pairwise_bot_iff
 #align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iff
+-/
 
 alias is_clique_bot_iff ↔ is_clique.subsingleton _
 #align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingleton
@@ -135,6 +139,7 @@ theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s := by
 #align simple_graph.is_n_clique.mono SimpleGraph.IsNClique.mono
 -/
 
+#print SimpleGraph.isNClique_bot_iff /-
 @[simp]
 theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧ s.card = n :=
   by
@@ -143,6 +148,7 @@ theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧
   rintro rfl
   exact card_le_one.symm
 #align simple_graph.is_n_clique_bot_iff SimpleGraph.isNClique_bot_iff
+-/
 
 variable [DecidableEq α] {a b c : α}
 
@@ -193,6 +199,7 @@ theorem IsNClique.not_cliqueFree (hG : G.IsNClique n s) : ¬G.CliqueFree n := fu
 #align simple_graph.is_n_clique.not_clique_free SimpleGraph.IsNClique.not_cliqueFree
 -/
 
+#print SimpleGraph.not_cliqueFree_of_top_embedding /-
 theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n)) ↪g G) :
     ¬G.CliqueFree n :=
   by
@@ -208,7 +215,9 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
     Ne.def, Subtype.mk_eq_mk]
   exact (Function.Embedding.apply_eq_iff_eq _ _ _).symm.Not
 #align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embedding
+-/
 
+#print SimpleGraph.topEmbeddingOfNotCliqueFree /-
 /-- An embedding of a complete graph that witnesses the fact that the graph is not clique-free. -/
 noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     (⊤ : SimpleGraph (Fin n)) ↪g G :=
@@ -223,7 +232,9 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
   rw [← ha] at this 
   convert (embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
 #align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFree
+-/
 
+#print SimpleGraph.not_cliqueFree_iff /-
 theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : SimpleGraph (Fin n)) ↪g G) :=
   by
   constructor
@@ -231,23 +242,30 @@ theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : Sim
   · rintro ⟨f⟩
     exact not_clique_free_of_top_embedding f
 #align simple_graph.not_clique_free_iff SimpleGraph.not_cliqueFree_iff
+-/
 
+#print SimpleGraph.cliqueFree_iff /-
 theorem cliqueFree_iff {n : ℕ} : G.CliqueFree n ↔ IsEmpty ((⊤ : SimpleGraph (Fin n)) ↪g G) := by
   rw [← not_iff_not, not_clique_free_iff, not_isEmpty_iff]
 #align simple_graph.clique_free_iff SimpleGraph.cliqueFree_iff
+-/
 
+#print SimpleGraph.not_cliqueFree_card_of_top_embedding /-
 theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGraph α) ↪g G) :
     ¬G.CliqueFree (card α) := by
   rw [not_clique_free_iff]
   use (iso.complete_graph (Fintype.equivFin α)).symm.toEmbedding.trans f
 #align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embedding
+-/
 
+#print SimpleGraph.cliqueFree_bot /-
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n :=
   by
   rintro t ht
   rw [is_n_clique_bot_iff] at ht 
   linarith
 #align simple_graph.clique_free_bot SimpleGraph.cliqueFree_bot
+-/
 
 #print SimpleGraph.CliqueFree.mono /-
 theorem CliqueFree.mono (h : m ≤ n) : G.CliqueFree m → G.CliqueFree n :=

bump to nightly-2023-06-04-18

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

3fb4268b

Diff

@@ -221,7 +221,7 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     apply iso.complete_graph
     simpa using (Fintype.equivFin h.some).symm
   rw [← ha] at this 
-  convert(embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
+  convert (embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
 #align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFree
 
 theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : SimpleGraph (Fin n)) ↪g G) :=
@@ -287,7 +287,7 @@ variable (G) {n : ℕ} {a b c : α} {s : Finset α}
 #print SimpleGraph.cliqueSet /-
 /-- The `n`-cliques in a graph as a set. -/
 def cliqueSet (n : ℕ) : Set (Finset α) :=
-  { s | G.IsNClique n s }
+  {s | G.IsNClique n s}
 #align simple_graph.clique_set SimpleGraph.cliqueSet
 -/

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -163,7 +163,7 @@ theorem is3Clique_iff :
   refine' ⟨fun h => _, _⟩
   · obtain ⟨a, b, c, -, -, -, rfl⟩ := card_eq_three.1 h.card_eq
     refine' ⟨a, b, c, _⟩
-    rw [is_3_clique_triple_iff] at h
+    rw [is_3_clique_triple_iff] at h 
     tauto
   · rintro ⟨a, b, c, hab, hbc, hca, rfl⟩
     exact is_3_clique_triple_iff.2 ⟨hab, hbc, hca⟩
@@ -201,7 +201,7 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   simp only [card_map, Finset.card_fin, eq_self_iff_true, and_true_iff]
   ext (⟨v, hv⟩⟨w, hw⟩)
   simp only [coe_map, RelEmbedding.coe_toEmbedding, Set.mem_image, coe_univ, Set.mem_univ,
-    true_and_iff] at hv hw
+    true_and_iff] at hv hw 
   obtain ⟨v', rfl⟩ := hv
   obtain ⟨w', rfl⟩ := hw
   simp only [f.map_adj_iff, comap_adj, Function.Embedding.coe_subtype, Subtype.coe_mk, top_adj,
@@ -214,13 +214,13 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     (⊤ : SimpleGraph (Fin n)) ↪g G :=
   by
   simp only [clique_free, is_n_clique_iff, is_clique_iff_induce_eq, not_forall,
-    Classical.not_not] at h
+    Classical.not_not] at h 
   obtain ⟨ha, hb⟩ := h.some_spec
   have : (⊤ : SimpleGraph (Fin h.some.card)) ≃g (⊤ : SimpleGraph h.some) :=
     by
     apply iso.complete_graph
     simpa using (Fintype.equivFin h.some).symm
-  rw [← ha] at this
+  rw [← ha] at this 
   convert(embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
 #align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFree
 
@@ -245,7 +245,7 @@ theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGrap
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n :=
   by
   rintro t ht
-  rw [is_n_clique_bot_iff] at ht
+  rw [is_n_clique_bot_iff] at ht 
   linarith
 #align simple_graph.clique_free_bot SimpleGraph.cliqueFree_bot
 
@@ -270,7 +270,7 @@ theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :
   by
   by_contra h
   refine' Nat.lt_le_antisymm hc _
-  rw [clique_free_iff, not_isEmpty_iff] at h
+  rw [clique_free_iff, not_isEmpty_iff] at h 
   simpa using Fintype.card_le_of_embedding h.some.to_embedding
 #align simple_graph.clique_free_of_card_lt SimpleGraph.cliqueFree_of_card_lt
 -/

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -60,12 +60,6 @@ theorem isClique_iff : G.IsClique s ↔ s.Pairwise G.Adj :=
 #align simple_graph.is_clique_iff SimpleGraph.isClique_iff
 -/
 
-/- warning: simple_graph.is_clique_iff_induce_eq -> SimpleGraph.isClique_iff_induce_eq is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.completeBooleanAlgebra.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s))))))))
-but is expected to have type
-  forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (CompleteLattice.toTop.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.completeBooleanAlgebra.{u1} (Set.Elem.{u1} α s))))))))
-Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique_iff_induce_eq SimpleGraph.isClique_iff_induce_eqₓ'. -/
 /-- A clique is a set of vertices whose induced graph is complete. -/
 theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ :=
   by
@@ -98,23 +92,11 @@ theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t := by simp
 #align simple_graph.is_clique.subset SimpleGraph.IsClique.subset
 -/
 
-/- warning: simple_graph.is_clique_bot_iff -> SimpleGraph.isClique_bot_iff is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) (Set.Subsingleton.{u1} α s)
-but is expected to have type
-  forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) (Set.Subsingleton.{u1} α s)
-Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iffₓ'. -/
 @[simp]
 theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Subsingleton :=
   Set.pairwise_bot_iff
 #align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iff
 
-/- warning: simple_graph.is_clique.subsingleton -> SimpleGraph.IsClique.subsingleton is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) -> (Set.Subsingleton.{u1} α s)
-but is expected to have type
-  forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) -> (Set.Subsingleton.{u1} α s)
-Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingletonₓ'. -/
 alias is_clique_bot_iff ↔ is_clique.subsingleton _
 #align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingleton
 
@@ -153,12 +135,6 @@ theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s := by
 #align simple_graph.is_n_clique.mono SimpleGraph.IsNClique.mono
 -/
 
-/- warning: simple_graph.is_n_clique_bot_iff -> SimpleGraph.isNClique_bot_iff is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n s) (And (LE.le.{0} Nat Nat.hasLe n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
-but is expected to have type
-  forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n s) (And (LE.le.{0} Nat instLENat n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
-Case conversion may be inaccurate. Consider using '#align simple_graph.is_n_clique_bot_iff SimpleGraph.isNClique_bot_iffₓ'. -/
 @[simp]
 theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧ s.card = n :=
   by
@@ -217,12 +193,6 @@ theorem IsNClique.not_cliqueFree (hG : G.IsNClique n s) : ¬G.CliqueFree n := fu
 #align simple_graph.is_n_clique.not_clique_free SimpleGraph.IsNClique.not_cliqueFree
 -/
 
-/- warning: simple_graph.not_clique_free_of_top_embedding -> SimpleGraph.not_cliqueFree_of_top_embedding is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
-but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
-Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embeddingₓ'. -/
 theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n)) ↪g G) :
     ¬G.CliqueFree n :=
   by
@@ -239,12 +209,6 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   exact (Function.Embedding.apply_eq_iff_eq _ _ _).symm.Not
 #align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embedding
 
-/- warning: simple_graph.top_embedding_of_not_clique_free -> SimpleGraph.topEmbeddingOfNotCliqueFree is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G)
-but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G)
-Case conversion may be inaccurate. Consider using '#align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFreeₓ'. -/
 /-- An embedding of a complete graph that witnesses the fact that the graph is not clique-free. -/
 noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     (⊤ : SimpleGraph (Fin n)) ↪g G :=
@@ -260,12 +224,6 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
   convert(embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
 #align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFree
 
-/- warning: simple_graph.not_clique_free_iff -> SimpleGraph.not_cliqueFree_iff is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
-but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
-Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_iff SimpleGraph.not_cliqueFree_iffₓ'. -/
 theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : SimpleGraph (Fin n)) ↪g G) :=
   by
   constructor
@@ -274,34 +232,16 @@ theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : Sim
     exact not_clique_free_of_top_embedding f
 #align simple_graph.not_clique_free_iff SimpleGraph.not_cliqueFree_iff
 
-/- warning: simple_graph.clique_free_iff -> SimpleGraph.cliqueFree_iff is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
-but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
-Case conversion may be inaccurate. Consider using '#align simple_graph.clique_free_iff SimpleGraph.cliqueFree_iffₓ'. -/
 theorem cliqueFree_iff {n : ℕ} : G.CliqueFree n ↔ IsEmpty ((⊤ : SimpleGraph (Fin n)) ↪g G) := by
   rw [← not_iff_not, not_clique_free_iff, not_isEmpty_iff]
 #align simple_graph.clique_free_iff SimpleGraph.cliqueFree_iff
 
-/- warning: simple_graph.not_clique_free_card_of_top_embedding -> SimpleGraph.not_cliqueFree_card_of_top_embedding is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
-but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toTop.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
-Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embeddingₓ'. -/
 theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGraph α) ↪g G) :
     ¬G.CliqueFree (card α) := by
   rw [not_clique_free_iff]
   use (iso.complete_graph (Fintype.equivFin α)).symm.toEmbedding.trans f
 #align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embedding
 
-/- warning: simple_graph.clique_free_bot -> SimpleGraph.cliqueFree_bot is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat Nat.hasLe (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n)
-but is expected to have type
-  forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat instLENat (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n)
-Case conversion may be inaccurate. Consider using '#align simple_graph.clique_free_bot SimpleGraph.cliqueFree_botₓ'. -/
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n :=
   by
   rintro t ht

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -87,17 +87,13 @@ instance [DecidableEq α] [DecidableRel G.Adj] {s : Finset α} : Decidable (G.Is
 variable {G H}
 
 #print SimpleGraph.IsClique.mono /-
-theorem IsClique.mono (h : G ≤ H) : G.IsClique s → H.IsClique s :=
-  by
-  simp_rw [is_clique_iff]
+theorem IsClique.mono (h : G ≤ H) : G.IsClique s → H.IsClique s := by simp_rw [is_clique_iff];
   exact Set.Pairwise.mono' h
 #align simple_graph.is_clique.mono SimpleGraph.IsClique.mono
 -/
 
 #print SimpleGraph.IsClique.subset /-
-theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t :=
-  by
-  simp_rw [is_clique_iff]
+theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t := by simp_rw [is_clique_iff];
   exact Set.Pairwise.mono h
 #align simple_graph.is_clique.subset SimpleGraph.IsClique.subset
 -/
@@ -152,10 +148,8 @@ instance [DecidableEq α] [DecidableRel G.Adj] {n : ℕ} {s : Finset α} :
 variable {G H}
 
 #print SimpleGraph.IsNClique.mono /-
-theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s :=
-  by
-  simp_rw [is_n_clique_iff]
-  exact And.imp_left (is_clique.mono h)
+theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s := by
+  simp_rw [is_n_clique_iff]; exact And.imp_left (is_clique.mono h)
 #align simple_graph.is_n_clique.mono SimpleGraph.IsNClique.mono
 -/

bump to nightly-2023-04-20-10

mathlib commit https://github.com/leanprover-community/mathlib/commit/730c6d4cab72b9d84fcfb9e95e8796e9cd8f40ba

fbfe5c3e

Diff

@@ -236,7 +236,7 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   use finset.univ.map f.to_embedding
   simp only [card_map, Finset.card_fin, eq_self_iff_true, and_true_iff]
   ext (⟨v, hv⟩⟨w, hw⟩)
-  simp only [coe_map, RelEmbedding.coeFn_toEmbedding, Set.mem_image, coe_univ, Set.mem_univ,
+  simp only [coe_map, RelEmbedding.coe_toEmbedding, Set.mem_image, coe_univ, Set.mem_univ,
     true_and_iff] at hv hw
   obtain ⟨v', rfl⟩ := hv
   obtain ⟨w', rfl⟩ := hw

bump to nightly-2023-03-27-22

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

0f55b099

Diff

@@ -64,7 +64,7 @@ theorem isClique_iff : G.IsClique s ↔ s.Pairwise G.Adj :=
 lean 3 declaration is
   forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.completeBooleanAlgebra.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s))))))))
 but is expected to have type
-  forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} (Set.Elem.{u1} α s)))))
+  forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (CompleteLattice.toTop.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.completeBooleanAlgebra.{u1} (Set.Elem.{u1} α s))))))))
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique_iff_induce_eq SimpleGraph.isClique_iff_induce_eqₓ'. -/
 /-- A clique is a set of vertices whose induced graph is complete. -/
 theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ :=
@@ -106,7 +106,7 @@ theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t :=
 lean 3 declaration is
   forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) (Set.Subsingleton.{u1} α s)
 but is expected to have type
-  forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) s) (Set.Subsingleton.{u1} α s)
+  forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) (Set.Subsingleton.{u1} α s)
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iffₓ'. -/
 @[simp]
 theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Subsingleton :=
@@ -117,7 +117,7 @@ theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Su
 lean 3 declaration is
   forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) -> (Set.Subsingleton.{u1} α s)
 but is expected to have type
-  forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) s) -> (Set.Subsingleton.{u1} α s)
+  forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) -> (Set.Subsingleton.{u1} α s)
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingletonₓ'. -/
 alias is_clique_bot_iff ↔ is_clique.subsingleton _
 #align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingleton
@@ -163,7 +163,7 @@ theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s :=
 lean 3 declaration is
   forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n s) (And (LE.le.{0} Nat Nat.hasLe n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
 but is expected to have type
-  forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) n s) (And (LE.le.{0} Nat instLENat n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
+  forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n s) (And (LE.le.{0} Nat instLENat n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_n_clique_bot_iff SimpleGraph.isNClique_bot_iffₓ'. -/
 @[simp]
 theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧ s.card = n :=
@@ -227,7 +227,7 @@ theorem IsNClique.not_cliqueFree (hG : G.IsNClique n s) : ¬G.CliqueFree n := fu
 lean 3 declaration is
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
 but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
 Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embeddingₓ'. -/
 theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n)) ↪g G) :
     ¬G.CliqueFree n :=
@@ -249,7 +249,7 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
 lean 3 declaration is
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G)
 but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G)
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G)
 Case conversion may be inaccurate. Consider using '#align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFreeₓ'. -/
 /-- An embedding of a complete graph that witnesses the fact that the graph is not clique-free. -/
 noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
@@ -270,7 +270,7 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
 lean 3 declaration is
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
 but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G))
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
 Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_iff SimpleGraph.not_cliqueFree_iffₓ'. -/
 theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : SimpleGraph (Fin n)) ↪g G) :=
   by
@@ -284,7 +284,7 @@ theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : Sim
 lean 3 declaration is
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
 but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G))
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
 Case conversion may be inaccurate. Consider using '#align simple_graph.clique_free_iff SimpleGraph.cliqueFree_iffₓ'. -/
 theorem cliqueFree_iff {n : ℕ} : G.CliqueFree n ↔ IsEmpty ((⊤ : SimpleGraph (Fin n)) ↪g G) := by
   rw [← not_iff_not, not_clique_free_iff, not_isEmpty_iff]
@@ -294,7 +294,7 @@ theorem cliqueFree_iff {n : ℕ} : G.CliqueFree n ↔ IsEmpty ((⊤ : SimpleGrap
 lean 3 declaration is
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
 but is expected to have type
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toTop.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
 Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embeddingₓ'. -/
 theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGraph α) ↪g G) :
     ¬G.CliqueFree (card α) := by
@@ -306,7 +306,7 @@ theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGrap
 lean 3 declaration is
   forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat Nat.hasLe (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n)
 but is expected to have type
-  forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat instLENat (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) n)
+  forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat instLENat (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n)
 Case conversion may be inaccurate. Consider using '#align simple_graph.clique_free_bot SimpleGraph.cliqueFree_botₓ'. -/
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n :=
   by

bump to nightly-2023-03-17-00

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

c85864d4

Diff

@@ -263,7 +263,7 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     apply iso.complete_graph
     simpa using (Fintype.equivFin h.some).symm
   rw [← ha] at this
-  convert (embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
+  convert(embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
 #align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFree
 
 /- warning: simple_graph.not_clique_free_iff -> SimpleGraph.not_cliqueFree_iff is a dubious translation:

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: Yaël Dillies, Bhavik Mehta
 
 ! This file was ported from Lean 3 source module combinatorics.simple_graph.clique
-! leanprover-community/mathlib commit cd7f0626a0b04be1dda223a26123313514a55fb4
+! leanprover-community/mathlib commit ee05e9ce1322178f0c12004eb93c00d2c8c00ed2
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -14,6 +14,9 @@ import Mathbin.Data.Finset.Pairwise
 /-!
 # Graph cliques
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This file defines cliques in simple graphs. A clique is a set of vertices that are pairwise
 adjacent.
 
@@ -59,7 +62,7 @@ theorem isClique_iff : G.IsClique s ↔ s.Pairwise G.Adj :=
 
 /- warning: simple_graph.is_clique_iff_induce_eq -> SimpleGraph.isClique_iff_induce_eq is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (BooleanAlgebra.toHasTop.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.booleanAlgebra.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)))))
+  forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.completeBooleanAlgebra.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s))))))))
 but is expected to have type
   forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} (Set.Elem.{u1} α s)))))
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique_iff_induce_eq SimpleGraph.isClique_iff_induce_eqₓ'. -/
@@ -101,7 +104,7 @@ theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t :=
 
 /- warning: simple_graph.is_clique_bot_iff -> SimpleGraph.isClique_bot_iff is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) s) (Set.Subsingleton.{u1} α s)
+  forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) (Set.Subsingleton.{u1} α s)
 but is expected to have type
   forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) s) (Set.Subsingleton.{u1} α s)
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iffₓ'. -/
@@ -112,7 +115,7 @@ theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Su
 
 /- warning: simple_graph.is_clique.subsingleton -> SimpleGraph.IsClique.subsingleton is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) s) -> (Set.Subsingleton.{u1} α s)
+  forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) s) -> (Set.Subsingleton.{u1} α s)
 but is expected to have type
   forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) s) -> (Set.Subsingleton.{u1} α s)
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingletonₓ'. -/
@@ -158,7 +161,7 @@ theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s :=
 
 /- warning: simple_graph.is_n_clique_bot_iff -> SimpleGraph.isNClique_bot_iff is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) n s) (And (LE.le.{0} Nat Nat.hasLe n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
+  forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n s) (And (LE.le.{0} Nat Nat.hasLe n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
 but is expected to have type
   forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) n s) (And (LE.le.{0} Nat instLENat n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
 Case conversion may be inaccurate. Consider using '#align simple_graph.is_n_clique_bot_iff SimpleGraph.isNClique_bot_iffₓ'. -/
@@ -222,7 +225,7 @@ theorem IsNClique.not_cliqueFree (hG : G.IsNClique n s) : ¬G.CliqueFree n := fu
 
 /- warning: simple_graph.not_clique_free_of_top_embedding -> SimpleGraph.not_cliqueFree_of_top_embedding is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.booleanAlgebra.{0} (Fin n)))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
 but is expected to have type
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
 Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embeddingₓ'. -/
@@ -244,7 +247,7 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
 
 /- warning: simple_graph.top_embedding_of_not_clique_free -> SimpleGraph.topEmbeddingOfNotCliqueFree is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.booleanAlgebra.{0} (Fin n)))) G)
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G)
 but is expected to have type
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G)
 Case conversion may be inaccurate. Consider using '#align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFreeₓ'. -/
@@ -265,7 +268,7 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
 
 /- warning: simple_graph.not_clique_free_iff -> SimpleGraph.not_cliqueFree_iff is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.booleanAlgebra.{0} (Fin n)))) G))
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
 but is expected to have type
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G))
 Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_iff SimpleGraph.not_cliqueFree_iffₓ'. -/
@@ -279,7 +282,7 @@ theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : Sim
 
 /- warning: simple_graph.clique_free_iff -> SimpleGraph.cliqueFree_iff is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.booleanAlgebra.{0} (Fin n)))) G))
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (CompleteLattice.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (Order.Coframe.toCompleteLattice.{0} (SimpleGraph.{0} (Fin n)) (CompleteDistribLattice.toCoframe.{0} (SimpleGraph.{0} (Fin n)) (CompleteBooleanAlgebra.toCompleteDistribLattice.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.completeBooleanAlgebra.{0} (Fin n))))))) G))
 but is expected to have type
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G))
 Case conversion may be inaccurate. Consider using '#align simple_graph.clique_free_iff SimpleGraph.cliqueFree_iffₓ'. -/
@@ -289,7 +292,7 @@ theorem cliqueFree_iff {n : ℕ} : G.CliqueFree n ↔ IsEmpty ((⊤ : SimpleGrap
 
 /- warning: simple_graph.not_clique_free_card_of_top_embedding -> SimpleGraph.not_cliqueFree_card_of_top_embedding is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasTop.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasTop.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
 but is expected to have type
   forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
 Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embeddingₓ'. -/
@@ -301,7 +304,7 @@ theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGrap
 
 /- warning: simple_graph.clique_free_bot -> SimpleGraph.cliqueFree_bot is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat Nat.hasLe (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) n)
+  forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat Nat.hasLe (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (CompleteLattice.toHasBot.{u1} (SimpleGraph.{u1} α) (Order.Coframe.toCompleteLattice.{u1} (SimpleGraph.{u1} α) (CompleteDistribLattice.toCoframe.{u1} (SimpleGraph.{u1} α) (CompleteBooleanAlgebra.toCompleteDistribLattice.{u1} (SimpleGraph.{u1} α) (SimpleGraph.completeBooleanAlgebra.{u1} α)))))) n)
 but is expected to have type
   forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat instLENat (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) n)
 Case conversion may be inaccurate. Consider using '#align simple_graph.clique_free_bot SimpleGraph.cliqueFree_botₓ'. -/

bump to nightly-2023-02-27-16

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

feafc24f

Diff

@@ -44,15 +44,25 @@ section Clique
 
 variable {s t : Set α}
 
+#print SimpleGraph.IsClique /-
 /-- A clique in a graph is a set of vertices that are pairwise adjacent. -/
 abbrev IsClique (s : Set α) : Prop :=
   s.Pairwise G.Adj
 #align simple_graph.is_clique SimpleGraph.IsClique
+-/
 
+#print SimpleGraph.isClique_iff /-
 theorem isClique_iff : G.IsClique s ↔ s.Pairwise G.Adj :=
   Iff.rfl
 #align simple_graph.is_clique_iff SimpleGraph.isClique_iff
+-/
 
+/- warning: simple_graph.is_clique_iff_induce_eq -> SimpleGraph.isClique_iff_induce_eq is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (BooleanAlgebra.toHasTop.{u1} (SimpleGraph.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)) (SimpleGraph.booleanAlgebra.{u1} (coeSort.{succ u1, succ (succ u1)} (Set.{u1} α) Type.{u1} (Set.hasCoeToSort.{u1} α) s)))))
+but is expected to have type
+  forall {α : Type.{u1}} (G : SimpleGraph.{u1} α) {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α G s) (Eq.{succ u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.induce.{u1} α s G) (Top.top.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} (Set.Elem.{u1} α s)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} (Set.Elem.{u1} α s)))))
+Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique_iff_induce_eq SimpleGraph.isClique_iff_induce_eqₓ'. -/
 /-- A clique is a set of vertices whose induced graph is complete. -/
 theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ :=
   by
@@ -73,23 +83,39 @@ instance [DecidableEq α] [DecidableRel G.Adj] {s : Finset α} : Decidable (G.Is
 
 variable {G H}
 
+#print SimpleGraph.IsClique.mono /-
 theorem IsClique.mono (h : G ≤ H) : G.IsClique s → H.IsClique s :=
   by
   simp_rw [is_clique_iff]
   exact Set.Pairwise.mono' h
 #align simple_graph.is_clique.mono SimpleGraph.IsClique.mono
+-/
 
+#print SimpleGraph.IsClique.subset /-
 theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t :=
   by
   simp_rw [is_clique_iff]
   exact Set.Pairwise.mono h
 #align simple_graph.is_clique.subset SimpleGraph.IsClique.subset
+-/
 
+/- warning: simple_graph.is_clique_bot_iff -> SimpleGraph.isClique_bot_iff is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) s) (Set.Subsingleton.{u1} α s)
+but is expected to have type
+  forall {α : Type.{u1}} {s : Set.{u1} α}, Iff (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) s) (Set.Subsingleton.{u1} α s)
+Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iffₓ'. -/
 @[simp]
 theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Subsingleton :=
   Set.pairwise_bot_iff
 #align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iff
 
+/- warning: simple_graph.is_clique.subsingleton -> SimpleGraph.IsClique.subsingleton is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) s) -> (Set.Subsingleton.{u1} α s)
+but is expected to have type
+  forall {α : Type.{u1}} {s : Set.{u1} α}, (SimpleGraph.IsClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) s) -> (Set.Subsingleton.{u1} α s)
+Case conversion may be inaccurate. Consider using '#align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingletonₓ'. -/
 alias is_clique_bot_iff ↔ is_clique.subsingleton _
 #align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingleton
 
@@ -102,15 +128,19 @@ section NClique
 
 variable {n : ℕ} {s : Finset α}
 
+#print SimpleGraph.IsNClique /-
 /-- A `n`-clique in a graph is a set of `n` vertices which are pairwise connected. -/
 structure IsNClique (n : ℕ) (s : Finset α) : Prop where
   clique : G.IsClique s
   card_eq : s.card = n
 #align simple_graph.is_n_clique SimpleGraph.IsNClique
+-/
 
+#print SimpleGraph.isNClique_iff /-
 theorem isNClique_iff : G.IsNClique n s ↔ G.IsClique s ∧ s.card = n :=
   ⟨fun h => ⟨h.1, h.2⟩, fun h => ⟨h.1, h.2⟩⟩
 #align simple_graph.is_n_clique_iff SimpleGraph.isNClique_iff
+-/
 
 instance [DecidableEq α] [DecidableRel G.Adj] {n : ℕ} {s : Finset α} :
     Decidable (G.IsNClique n s) :=
@@ -118,12 +148,20 @@ instance [DecidableEq α] [DecidableRel G.Adj] {n : ℕ} {s : Finset α} :
 
 variable {G H}
 
+#print SimpleGraph.IsNClique.mono /-
 theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s :=
   by
   simp_rw [is_n_clique_iff]
   exact And.imp_left (is_clique.mono h)
 #align simple_graph.is_n_clique.mono SimpleGraph.IsNClique.mono
+-/
 
+/- warning: simple_graph.is_n_clique_bot_iff -> SimpleGraph.isNClique_bot_iff is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) n s) (And (LE.le.{0} Nat Nat.hasLe n (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
+but is expected to have type
+  forall {α : Type.{u1}} {n : Nat} {s : Finset.{u1} α}, Iff (SimpleGraph.IsNClique.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) n s) (And (LE.le.{0} Nat instLENat n (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (Eq.{1} Nat (Finset.card.{u1} α s) n))
+Case conversion may be inaccurate. Consider using '#align simple_graph.is_n_clique_bot_iff SimpleGraph.isNClique_bot_iffₓ'. -/
 @[simp]
 theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧ s.card = n :=
   by
@@ -135,15 +173,18 @@ theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧
 
 variable [DecidableEq α] {a b c : α}
 
-theorem is_3_clique_triple_iff : G.IsNClique 3 {a, b, c} ↔ G.Adj a b ∧ G.Adj a c ∧ G.Adj b c :=
+#print SimpleGraph.is3Clique_triple_iff /-
+theorem is3Clique_triple_iff : G.IsNClique 3 {a, b, c} ↔ G.Adj a b ∧ G.Adj a c ∧ G.Adj b c :=
   by
   simp only [is_n_clique_iff, is_clique_iff, Set.pairwise_insert_of_symmetric G.symm, coe_insert]
   have : ¬1 + 1 = 3 := by norm_num
   by_cases hab : a = b <;> by_cases hbc : b = c <;> by_cases hac : a = c <;> subst_vars <;>
     simp [G.ne_of_adj, and_rotate, *]
-#align simple_graph.is_3_clique_triple_iff SimpleGraph.is_3_clique_triple_iff
+#align simple_graph.is_3_clique_triple_iff SimpleGraph.is3Clique_triple_iff
+-/
 
-theorem is_3_clique_iff :
+#print SimpleGraph.is3Clique_iff /-
+theorem is3Clique_iff :
     G.IsNClique 3 s ↔ ∃ a b c, G.Adj a b ∧ G.Adj a c ∧ G.Adj b c ∧ s = {a, b, c} :=
   by
   refine' ⟨fun h => _, _⟩
@@ -153,7 +194,8 @@ theorem is_3_clique_iff :
     tauto
   · rintro ⟨a, b, c, hab, hbc, hca, rfl⟩
     exact is_3_clique_triple_iff.2 ⟨hab, hbc, hca⟩
-#align simple_graph.is_3_clique_iff SimpleGraph.is_3_clique_iff
+#align simple_graph.is_3_clique_iff SimpleGraph.is3Clique_iff
+-/
 
 end NClique
 
@@ -164,16 +206,26 @@ section CliqueFree
 
 variable {m n : ℕ}
 
+#print SimpleGraph.CliqueFree /-
 /-- `G.clique_free n` means that `G` has no `n`-cliques. -/
 def CliqueFree (n : ℕ) : Prop :=
   ∀ t, ¬G.IsNClique n t
 #align simple_graph.clique_free SimpleGraph.CliqueFree
+-/
 
 variable {G H} {s : Finset α}
 
+#print SimpleGraph.IsNClique.not_cliqueFree /-
 theorem IsNClique.not_cliqueFree (hG : G.IsNClique n s) : ¬G.CliqueFree n := fun h => h _ hG
 #align simple_graph.is_n_clique.not_clique_free SimpleGraph.IsNClique.not_cliqueFree
+-/
 
+/- warning: simple_graph.not_clique_free_of_top_embedding -> SimpleGraph.not_cliqueFree_of_top_embedding is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.booleanAlgebra.{0} (Fin n)))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
+but is expected to have type
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G n))
+Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embeddingₓ'. -/
 theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n)) ↪g G) :
     ¬G.CliqueFree n :=
   by
@@ -190,6 +242,12 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   exact (Function.Embedding.apply_eq_iff_eq _ _ _).symm.Not
 #align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embedding
 
+/- warning: simple_graph.top_embedding_of_not_clique_free -> SimpleGraph.topEmbeddingOfNotCliqueFree is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.booleanAlgebra.{0} (Fin n)))) G)
+but is expected to have type
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, (Not (SimpleGraph.CliqueFree.{u1} α G n)) -> (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G)
+Case conversion may be inaccurate. Consider using '#align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFreeₓ'. -/
 /-- An embedding of a complete graph that witnesses the fact that the graph is not clique-free. -/
 noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     (⊤ : SimpleGraph (Fin n)) ↪g G :=
@@ -205,6 +263,12 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
   convert (embedding.induce ↑h.some).comp this.to_embedding <;> exact hb.symm
 #align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFree
 
+/- warning: simple_graph.not_clique_free_iff -> SimpleGraph.not_cliqueFree_iff is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.booleanAlgebra.{0} (Fin n)))) G))
+but is expected to have type
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} (n : Nat), Iff (Not (SimpleGraph.CliqueFree.{u1} α G n)) (Nonempty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G))
+Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_iff SimpleGraph.not_cliqueFree_iffₓ'. -/
 theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : SimpleGraph (Fin n)) ↪g G) :=
   by
   constructor
@@ -213,16 +277,34 @@ theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : Sim
     exact not_clique_free_of_top_embedding f
 #align simple_graph.not_clique_free_iff SimpleGraph.not_cliqueFree_iff
 
+/- warning: simple_graph.clique_free_iff -> SimpleGraph.cliqueFree_iff is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toHasTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.booleanAlgebra.{0} (Fin n)))) G))
+but is expected to have type
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} {n : Nat}, Iff (SimpleGraph.CliqueFree.{u1} α G n) (IsEmpty.{succ u1} (SimpleGraph.Embedding.{0, u1} (Fin n) α (Top.top.{0} (SimpleGraph.{0} (Fin n)) (BooleanAlgebra.toTop.{0} (SimpleGraph.{0} (Fin n)) (SimpleGraph.instBooleanAlgebraSimpleGraph.{0} (Fin n)))) G))
+Case conversion may be inaccurate. Consider using '#align simple_graph.clique_free_iff SimpleGraph.cliqueFree_iffₓ'. -/
 theorem cliqueFree_iff {n : ℕ} : G.CliqueFree n ↔ IsEmpty ((⊤ : SimpleGraph (Fin n)) ↪g G) := by
   rw [← not_iff_not, not_clique_free_iff, not_isEmpty_iff]
 #align simple_graph.clique_free_iff SimpleGraph.cliqueFree_iff
 
+/- warning: simple_graph.not_clique_free_card_of_top_embedding -> SimpleGraph.not_cliqueFree_card_of_top_embedding is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasTop.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
+but is expected to have type
+  forall {α : Type.{u1}} {G : SimpleGraph.{u1} α} [_inst_1 : Fintype.{u1} α], (SimpleGraph.Embedding.{u1, u1} α α (Top.top.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toTop.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) G) -> (Not (SimpleGraph.CliqueFree.{u1} α G (Fintype.card.{u1} α _inst_1)))
+Case conversion may be inaccurate. Consider using '#align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embeddingₓ'. -/
 theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGraph α) ↪g G) :
     ¬G.CliqueFree (card α) := by
   rw [not_clique_free_iff]
   use (iso.complete_graph (Fintype.equivFin α)).symm.toEmbedding.trans f
 #align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embedding
 
+/- warning: simple_graph.clique_free_bot -> SimpleGraph.cliqueFree_bot is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat Nat.hasLe (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toHasBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.booleanAlgebra.{u1} α))) n)
+but is expected to have type
+  forall {α : Type.{u1}} {n : Nat}, (LE.le.{0} Nat instLENat (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) n) -> (SimpleGraph.CliqueFree.{u1} α (Bot.bot.{u1} (SimpleGraph.{u1} α) (BooleanAlgebra.toBot.{u1} (SimpleGraph.{u1} α) (SimpleGraph.instBooleanAlgebraSimpleGraph.{u1} α))) n)
+Case conversion may be inaccurate. Consider using '#align simple_graph.clique_free_bot SimpleGraph.cliqueFree_botₓ'. -/
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n :=
   by
   rintro t ht
@@ -230,17 +312,22 @@ theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n :=
   linarith
 #align simple_graph.clique_free_bot SimpleGraph.cliqueFree_bot
 
+#print SimpleGraph.CliqueFree.mono /-
 theorem CliqueFree.mono (h : m ≤ n) : G.CliqueFree m → G.CliqueFree n :=
   by
   rintro hG s hs
   obtain ⟨t, hts, ht⟩ := s.exists_smaller_set _ (h.trans hs.card_eq.ge)
   exact hG _ ⟨hs.clique.subset hts, ht⟩
 #align simple_graph.clique_free.mono SimpleGraph.CliqueFree.mono
+-/
 
+#print SimpleGraph.CliqueFree.anti /-
 theorem CliqueFree.anti (h : G ≤ H) : H.CliqueFree n → G.CliqueFree n :=
   forall_imp fun s => mt <| IsNClique.mono h
 #align simple_graph.clique_free.anti SimpleGraph.CliqueFree.anti
+-/
 
+#print SimpleGraph.cliqueFree_of_card_lt /-
 /-- See `simple_graph.clique_free_chromatic_number_succ` for a tighter bound. -/
 theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :=
   by
@@ -249,6 +336,7 @@ theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :
   rw [clique_free_iff, not_isEmpty_iff] at h
   simpa using Fintype.card_le_of_embedding h.some.to_embedding
 #align simple_graph.clique_free_of_card_lt SimpleGraph.cliqueFree_of_card_lt
+-/
 
 end CliqueFree
 
@@ -259,19 +347,25 @@ section CliqueSet
 
 variable (G) {n : ℕ} {a b c : α} {s : Finset α}
 
+#print SimpleGraph.cliqueSet /-
 /-- The `n`-cliques in a graph as a set. -/
 def cliqueSet (n : ℕ) : Set (Finset α) :=
   { s | G.IsNClique n s }
 #align simple_graph.clique_set SimpleGraph.cliqueSet
+-/
 
+#print SimpleGraph.mem_cliqueSet_iff /-
 theorem mem_cliqueSet_iff : s ∈ G.cliqueSet n ↔ G.IsNClique n s :=
   Iff.rfl
 #align simple_graph.mem_clique_set_iff SimpleGraph.mem_cliqueSet_iff
+-/
 
+#print SimpleGraph.cliqueSet_eq_empty_iff /-
 @[simp]
 theorem cliqueSet_eq_empty_iff : G.cliqueSet n = ∅ ↔ G.CliqueFree n := by
   simp_rw [clique_free, Set.eq_empty_iff_forall_not_mem, mem_clique_set_iff]
 #align simple_graph.clique_set_eq_empty_iff SimpleGraph.cliqueSet_eq_empty_iff
+-/
 
 alias clique_set_eq_empty_iff ↔ _ clique_free.clique_set
 #align simple_graph.clique_free.clique_set SimpleGraph.CliqueFree.cliqueSet
@@ -280,12 +374,16 @@ attribute [protected] clique_free.clique_set
 
 variable {G H}
 
+#print SimpleGraph.cliqueSet_mono /-
 @[mono]
 theorem cliqueSet_mono (h : G ≤ H) : G.cliqueSet n ⊆ H.cliqueSet n := fun _ => IsNClique.mono h
 #align simple_graph.clique_set_mono SimpleGraph.cliqueSet_mono
+-/
 
+#print SimpleGraph.cliqueSet_mono' /-
 theorem cliqueSet_mono' (h : G ≤ H) : G.cliqueSet ≤ H.cliqueSet := fun _ => cliqueSet_mono h
 #align simple_graph.clique_set_mono' SimpleGraph.cliqueSet_mono'
+-/
 
 end CliqueSet
 
@@ -296,24 +394,32 @@ section CliqueFinset
 
 variable (G) [Fintype α] [DecidableEq α] [DecidableRel G.Adj] {n : ℕ} {a b c : α} {s : Finset α}
 
+#print SimpleGraph.cliqueFinset /-
 /-- The `n`-cliques in a graph as a finset. -/
 def cliqueFinset (n : ℕ) : Finset (Finset α) :=
   univ.filterₓ <| G.IsNClique n
 #align simple_graph.clique_finset SimpleGraph.cliqueFinset
+-/
 
+#print SimpleGraph.mem_cliqueFinset_iff /-
 theorem mem_cliqueFinset_iff : s ∈ G.cliqueFinset n ↔ G.IsNClique n s :=
   mem_filter.trans <| and_iff_right <| mem_univ _
 #align simple_graph.mem_clique_finset_iff SimpleGraph.mem_cliqueFinset_iff
+-/
 
+#print SimpleGraph.coe_cliqueFinset /-
 @[simp]
 theorem coe_cliqueFinset (n : ℕ) : (G.cliqueFinset n : Set (Finset α)) = G.cliqueSet n :=
   Set.ext fun _ => mem_cliqueFinset_iff _
 #align simple_graph.coe_clique_finset SimpleGraph.coe_cliqueFinset
+-/
 
+#print SimpleGraph.cliqueFinset_eq_empty_iff /-
 @[simp]
 theorem cliqueFinset_eq_empty_iff : G.cliqueFinset n = ∅ ↔ G.CliqueFree n := by
   simp_rw [clique_free, eq_empty_iff_forall_not_mem, mem_clique_finset_iff]
 #align simple_graph.clique_finset_eq_empty_iff SimpleGraph.cliqueFinset_eq_empty_iff
+-/
 
 alias clique_finset_eq_empty_iff ↔ _ _root_.simple_graph.clique_free.clique_finset
 #align simple_graph.clique_free.clique_finset SimpleGraph.CliqueFree.cliqueFinset
@@ -322,10 +428,12 @@ attribute [protected] clique_free.clique_finset
 
 variable {G} [DecidableRel H.Adj]
 
+#print SimpleGraph.cliqueFinset_mono /-
 @[mono]
 theorem cliqueFinset_mono (h : G ≤ H) : G.cliqueFinset n ⊆ H.cliqueFinset n :=
   monotone_filter_right _ fun _ => IsNClique.mono h
 #align simple_graph.clique_finset_mono SimpleGraph.cliqueFinset_mono
+-/
 
 end CliqueFinset

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

refactor: move SimpleGraph.Iso.card_edgeFinset_eq to untangle imports (#11817)

The single and currently unused theorem card_edgeFinset_eq in Combinatorics.SimpleGraph.Maps causes a dependency of that file on Combinatorics.SimpleGraph.Finite, which is problematic because the key concepts of Maps don't depend on graph finiteness at all. This commit moves the offending theorem to Operations in anticipation of #9317.

9d0b2332

Diff

@@ -3,11 +3,9 @@ Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
 -/
-import Mathlib.Combinatorics.SimpleGraph.Maps
-import Mathlib.Combinatorics.SimpleGraph.Operations
 import Mathlib.Combinatorics.SimpleGraph.Connectivity
+import Mathlib.Combinatorics.SimpleGraph.Operations
 import Mathlib.Data.Finset.Pairwise
-import Mathlib.Data.Finset.Preimage
 
 #align_import combinatorics.simple_graph.clique from "leanprover-community/mathlib"@"3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe"

chore(SimpleGraph/Clique): drop a DecidableEq assumption (#11811)

a87bb680

Diff

@@ -176,6 +176,8 @@ theorem isNClique_one : G.IsNClique 1 s ↔ ∃ a, s = {a} := by
   simp only [isNClique_iff, card_eq_one, and_iff_right_iff_imp]; rintro ⟨a, rfl⟩; simp
 #align simple_graph.is_n_clique_one SimpleGraph.isNClique_one
 
+section DecidableEq
+
 variable [DecidableEq α]
 
 theorem IsNClique.insert (hs : G.IsNClique n s) (h : ∀ b ∈ s, G.Adj a b) :
@@ -202,8 +204,11 @@ theorem is3Clique_iff :
     exact is3Clique_triple_iff.2 ⟨hab, hbc, hca⟩
 #align simple_graph.is_3_clique_iff SimpleGraph.is3Clique_iff
 
+end DecidableEq
+
 theorem is3Clique_iff_exists_cycle_length_three :
     (∃ s : Finset α, G.IsNClique 3 s) ↔ ∃ (u : α) (w : G.Walk u u), w.IsCycle ∧ w.length = 3 := by
+  classical
   simp_rw [is3Clique_iff, isCycle_def]
   exact
     ⟨(fun ⟨_, a, _, _, hab, hac, hbc, _⟩ => ⟨a, cons hab (cons hbc (cons hac.symm nil)), by aesop⟩),

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

1b40c7bc

Diff

@@ -59,7 +59,7 @@ theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ := by
   constructor
   · intro h
     ext ⟨v, hv⟩ ⟨w, hw⟩
-    simp only [comap_adj, Subtype.coe_mk, top_adj, Ne.def, Subtype.mk_eq_mk]
+    simp only [comap_adj, Subtype.coe_mk, top_adj, Ne, Subtype.mk_eq_mk]
     exact ⟨Adj.ne, h hv hw⟩
   · intro h v hv w hw hne
     have h2 : (G.induce s).Adj ⟨v, hv⟩ ⟨w, hw⟩ = _ := rfl

feat(Combinatorics/SimpleGraph): A graph has 3-clique iff it has a cycle of length 3 (#11434)

This is nice to have because when combined with is3Clique_iff, we will be able to prove that a graph has a cycle by just proving that 3 vertices are pairwise adjacent.

Co-authored-by: Rida <106540880+Rida-Hamadani@users.noreply.github.com>

e899dfee

Diff

@@ -5,6 +5,7 @@ Authors: Yaël Dillies, Bhavik Mehta
 -/
 import Mathlib.Combinatorics.SimpleGraph.Maps
 import Mathlib.Combinatorics.SimpleGraph.Operations
+import Mathlib.Combinatorics.SimpleGraph.Connectivity
 import Mathlib.Data.Finset.Pairwise
 import Mathlib.Data.Finset.Preimage
 
@@ -30,7 +31,7 @@ adjacent.
 -/
 
 
-open Finset Fintype Function
+open Finset Fintype Function SimpleGraph.Walk
 
 namespace SimpleGraph
 
@@ -201,6 +202,13 @@ theorem is3Clique_iff :
     exact is3Clique_triple_iff.2 ⟨hab, hbc, hca⟩
 #align simple_graph.is_3_clique_iff SimpleGraph.is3Clique_iff
 
+theorem is3Clique_iff_exists_cycle_length_three :
+    (∃ s : Finset α, G.IsNClique 3 s) ↔ ∃ (u : α) (w : G.Walk u u), w.IsCycle ∧ w.length = 3 := by
+  simp_rw [is3Clique_iff, isCycle_def]
+  exact
+    ⟨(fun ⟨_, a, _, _, hab, hac, hbc, _⟩ => ⟨a, cons hab (cons hbc (cons hac.symm nil)), by aesop⟩),
+    (fun ⟨_, .cons hab (.cons hbc (.cons hca nil)), _, _⟩ => ⟨_, _, _, _, hab, hca.symm, hbc, rfl⟩)⟩
+
 end NClique
 
 /-! ### Graphs without cliques -/

From https://github.com/leanprover-community/mathlib4/pull/9267#discussion_r1451605191:

refactor: single-edge graph (#9736)

I would prefer we use lattice operations for adding edges. The idea is to make constructor SimpleGraph.edge (v w : V) : SimpleGraph V that creates a graph with a single edge between v and w if they're not equal (and no edge if they are), and then G.addEdge v w would instead be G ⊔ edge v w. This is more versatile, though perhaps lemmas such as addEdge_of_adj are a bit more brittle to apply.

69fd837a

Diff

@@ -338,8 +338,8 @@ theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
 #align simple_graph.clique_free_two SimpleGraph.cliqueFree_two
 
 /-- Adding an edge increases the clique number by at most one. -/
-protected theorem CliqueFree.addEdge (h : G.CliqueFree n) (v w) :
-    (G.addEdge v w).CliqueFree (n + 1) := by
+protected theorem CliqueFree.sup_edge (h : G.CliqueFree n) (v w : α) :
+    (G ⊔ edge v w).CliqueFree (n + 1) := by
   contrapose h
   obtain ⟨f, ha⟩ := topEmbeddingOfNotCliqueFree h
   simp only [ne_eq, top_adj] at ha
@@ -354,7 +354,8 @@ protected theorem CliqueFree.addEdge (h : G.CliqueFree n) (v w) :
       (hx ▸ f.apply_eq_iff_eq x (x.succAbove a)).ne.mpr (x.succAbove_ne a).symm
     have ib : w ≠ f (x.succAbove b) :=
       (hx ▸ f.apply_eq_iff_eq x (x.succAbove b)).ne.mpr (x.succAbove_ne b).symm
-    simp only [addEdge, ia, ib, and_false, false_and, or_false] at hs
+    rw [sup_adj, edge_adj] at hs
+    simp only [ia.symm, ib.symm, and_false, false_and, or_false] at hs
     rw [hs, Fin.succAbove_right_inj]
   · use ⟨f ∘ Fin.succEmb n, (f.2.of_comp_iff _).mpr (RelEmbedding.injective _)⟩
     intro a b
@@ -362,7 +363,8 @@ protected theorem CliqueFree.addEdge (h : G.CliqueFree n) (v w) :
     have hs := @ha a.succ b.succ
     have ia : f a.succ ≠ w := by simp_all
     have ib : f b.succ ≠ w := by simp_all
-    simp only [addEdge, ia.symm, ib.symm, and_false, false_and, or_false] at hs
+    rw [sup_adj, edge_adj] at hs
+    simp only [ia, ib, and_false, false_and, or_false] at hs
     rw [hs, Fin.succ_inj]
 
 end CliqueFree

feat(Data/Fin/Basic): Improvement and extension of order results (#10156)

Refines and extends results relating to the monotonicity of succ, castSucc, and related functions

a55d1223

Diff

@@ -356,9 +356,9 @@ protected theorem CliqueFree.addEdge (h : G.CliqueFree n) (v w) :
       (hx ▸ f.apply_eq_iff_eq x (x.succAbove b)).ne.mpr (x.succAbove_ne b).symm
     simp only [addEdge, ia, ib, and_false, false_and, or_false] at hs
     rw [hs, Fin.succAbove_right_inj]
-  · use ⟨f ∘ Fin.succEmbedding n, (f.2.of_comp_iff _).mpr (RelEmbedding.injective _)⟩
+  · use ⟨f ∘ Fin.succEmb n, (f.2.of_comp_iff _).mpr (RelEmbedding.injective _)⟩
     intro a b
-    simp only [Fin.val_succEmbedding, Embedding.coeFn_mk, comp_apply, top_adj]
+    simp only [Fin.val_succEmb, Embedding.coeFn_mk, comp_apply, top_adj]
     have hs := @ha a.succ b.succ
     have ia : f a.succ ≠ w := by simp_all
     have ib : f b.succ ≠ w := by simp_all

feat: transfer of graph properties over maps (#9708)

Part of #9317.

6219c283

Diff

@@ -281,6 +281,11 @@ theorem CliqueFree.anti (h : G ≤ H) : H.CliqueFree n → G.CliqueFree n :=
   forall_imp fun _ ↦ mt <| IsNClique.mono h
 #align simple_graph.clique_free.anti SimpleGraph.CliqueFree.anti
 
+/-- If a graph is cliquefree, any graph that embeds into it is also cliquefree. -/
+theorem CliqueFree.comap {H : SimpleGraph β} (f : H ↪g G) : G.CliqueFree n → H.CliqueFree n := by
+  intro h; contrapose h
+  exact not_cliqueFree_of_top_embedding <| f.comp (topEmbeddingOfNotCliqueFree h)
+
 /-- See `SimpleGraph.cliqueFree_of_chromaticNumber_lt` for a tighter bound. -/
 theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n := by
   by_contra h

feat: local graph operations (#9267)

ba19db4d

Diff

@@ -299,41 +299,28 @@ theorem cliqueFree_completeMultipartiteGraph {ι : Type*} [Fintype ι] (V : ι 
   exact absurd he hn
 
 /-- Clique-freeness is preserved by `replaceVertex`. -/
-theorem cliqueFree_of_replaceVertex_cliqueFree [DecidableEq α] (s t : α) (h : G.CliqueFree n) :
+protected theorem CliqueFree.replaceVertex [DecidableEq α] (h : G.CliqueFree n) (s t : α) :
     (G.replaceVertex s t).CliqueFree n := by
   contrapose h
-  obtain ⟨⟨f, hi⟩, ha⟩ := topEmbeddingOfNotCliqueFree h
-  simp only [Function.Embedding.coeFn_mk, top_adj, ne_eq] at ha
+  obtain ⟨φ, hφ⟩ := topEmbeddingOfNotCliqueFree h
   rw [not_cliqueFree_iff]
-  by_cases mt : t ∈ Set.range f
+  by_cases mt : t ∈ Set.range φ
   · obtain ⟨x, hx⟩ := mt
-    by_cases ms : s ∈ Set.range f
+    by_cases ms : s ∈ Set.range φ
     · obtain ⟨y, hy⟩ := ms
-      by_cases hst : s = t
-      · simp_all [not_cliqueFree_iff]
-      · replace ha := @ha x y; simp_all
-    · use ⟨fun v => if v = x then s else f v, ?_⟩
-      swap
-      · intro a b
-        dsimp only
-        split_ifs
-        · simp_all
-        · intro; simp_all
-        · intro; simp_all
-        · apply hi
+      have e := @hφ x y
+      simp_rw [hx, hy, adj_comm, not_adj_replaceVertex_same, top_adj, false_iff, not_ne_iff] at e
+      rwa [← hx, e, hy, replaceVertex_self, not_cliqueFree_iff] at h
+    · unfold replaceVertex at hφ
+      use φ.setValue x s
       intro a b
-      simp only [Function.Embedding.coeFn_mk, top_adj, ne_eq]
-      split_ifs with h1 h2 h2
-      · simp_all
-      · have := (@ha b x).mpr h2
-        split_ifs at this; subst h1; tauto
-      · have := (@ha a x).mpr h1
-        split_ifs at this; subst h2; tauto
-      · rw [← @ha a b]
-        have := (@hi a x).mt h1
-        have := (@hi b x).mt h2
-        simp_all
-  · use ⟨f, hi⟩; simp_all
+      simp only [Embedding.coeFn_mk, Embedding.setValue, not_exists.mp ms, ite_false]
+      rw [apply_ite (G.Adj · _), apply_ite (G.Adj _ ·), apply_ite (G.Adj _ ·)]
+      convert @hφ a b <;> simp only [← φ.apply_eq_iff_eq, SimpleGraph.irrefl, hx]
+  · use φ
+    simp_rw [Set.mem_range, not_exists, ← ne_eq] at mt
+    conv at hφ => enter [a, b]; rw [G.adj_replaceVertex_iff_of_ne _ (mt a) (mt b)]
+    exact hφ
 
 @[simp]
 theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
@@ -345,6 +332,34 @@ theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
     exact cliqueFree_bot le_rfl
 #align simple_graph.clique_free_two SimpleGraph.cliqueFree_two
 
+/-- Adding an edge increases the clique number by at most one. -/
+protected theorem CliqueFree.addEdge (h : G.CliqueFree n) (v w) :
+    (G.addEdge v w).CliqueFree (n + 1) := by
+  contrapose h
+  obtain ⟨f, ha⟩ := topEmbeddingOfNotCliqueFree h
+  simp only [ne_eq, top_adj] at ha
+  rw [not_cliqueFree_iff]
+  by_cases mw : w ∈ Set.range f
+  · obtain ⟨x, hx⟩ := mw
+    use ⟨f ∘ x.succAboveEmb, (f.2.of_comp_iff _).mpr (RelEmbedding.injective _)⟩
+    intro a b
+    simp_rw [Embedding.coeFn_mk, comp_apply, Fin.succAboveEmb_apply, top_adj]
+    have hs := @ha (x.succAbove a) (x.succAbove b)
+    have ia : w ≠ f (x.succAbove a) :=
+      (hx ▸ f.apply_eq_iff_eq x (x.succAbove a)).ne.mpr (x.succAbove_ne a).symm
+    have ib : w ≠ f (x.succAbove b) :=
+      (hx ▸ f.apply_eq_iff_eq x (x.succAbove b)).ne.mpr (x.succAbove_ne b).symm
+    simp only [addEdge, ia, ib, and_false, false_and, or_false] at hs
+    rw [hs, Fin.succAbove_right_inj]
+  · use ⟨f ∘ Fin.succEmbedding n, (f.2.of_comp_iff _).mpr (RelEmbedding.injective _)⟩
+    intro a b
+    simp only [Fin.val_succEmbedding, Embedding.coeFn_mk, comp_apply, top_adj]
+    have hs := @ha a.succ b.succ
+    have ia : f a.succ ≠ w := by simp_all
+    have ib : f b.succ ≠ w := by simp_all
+    simp only [addEdge, ia.symm, ib.symm, and_false, false_and, or_false] at hs
+    rw [hs, Fin.succ_inj]
+
 end CliqueFree
 
 section CliqueFreeOn

refactor: split graph maps into a new file (#9579)

A continuation from https://github.com/leanprover-community/mathlib4/pull/9267#discussion_r1437052000.

c147cdfc

Diff

@@ -3,6 +3,7 @@ Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
 -/
+import Mathlib.Combinatorics.SimpleGraph.Maps
 import Mathlib.Combinatorics.SimpleGraph.Operations
 import Mathlib.Data.Finset.Pairwise
 import Mathlib.Data.Finset.Preimage

feat: move replaceVertex to its own file (#9400)

f61a485e

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
 -/
-import Mathlib.Combinatorics.SimpleGraph.Basic
+import Mathlib.Combinatorics.SimpleGraph.Operations
 import Mathlib.Data.Finset.Pairwise
 import Mathlib.Data.Finset.Preimage

chore: rename Finset.card_doubleton to Finset.card_pair (#9379)

570a85ce

Diff

@@ -339,7 +339,7 @@ theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
   classical
   constructor
   · simp_rw [← edgeSet_eq_empty, Set.eq_empty_iff_forall_not_mem, Sym2.forall, mem_edgeSet]
-    exact fun h a b hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.ne⟩
+    exact fun h a b hab => h _ ⟨by simpa [hab.ne], card_pair hab.ne⟩
   · rintro rfl
     exact cliqueFree_bot le_rfl
 #align simple_graph.clique_free_two SimpleGraph.cliqueFree_two
@@ -396,7 +396,7 @@ theorem cliqueFreeOn_of_card_lt {s : Finset α} (h : s.card < n) : G.CliqueFreeO
 @[simp]
 theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by
   classical
-  refine' ⟨fun h a ha b hb _ hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.ne⟩, _⟩
+  refine' ⟨fun h a ha b hb _ hab => h _ ⟨by simpa [hab.ne], card_pair hab.ne⟩, _⟩
   · push_cast
     exact Set.insert_subset_iff.2 ⟨ha, Set.singleton_subset_iff.2 hb⟩
   simp only [CliqueFreeOn, isNClique_iff, card_eq_two, coe_subset, not_and, not_exists]

feat: More clique lemmas (#8007)

Forward port https://github.com/leanprover-community/mathlib/pull/19203

778aba64

Diff

@@ -5,8 +5,9 @@ Authors: Yaël Dillies, Bhavik Mehta
 -/
 import Mathlib.Combinatorics.SimpleGraph.Basic
 import Mathlib.Data.Finset.Pairwise
+import Mathlib.Data.Finset.Preimage
 
-#align_import combinatorics.simple_graph.clique from "leanprover-community/mathlib"@"cd7f0626a0b04be1dda223a26123313514a55fb4"
+#align_import combinatorics.simple_graph.clique from "leanprover-community/mathlib"@"3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe"
 
 /-!
 # Graph cliques
@@ -24,15 +25,15 @@ adjacent.
 ## TODO
 
 * Clique numbers
-* Do we need `cliqueSet`, a version of `cliqueFinset` for infinite graphs?
+* Dualise all the API to get independent sets
 -/
 
 
-open Finset Fintype
+open Finset Fintype Function
 
 namespace SimpleGraph
 
-variable {α : Type*} (G H : SimpleGraph α)
+variable {α β : Type*} (G H : SimpleGraph α)
 
 /-! ### Cliques -/
 
@@ -68,18 +69,43 @@ theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ := by
 instance [DecidableEq α] [DecidableRel G.Adj] {s : Finset α} : Decidable (G.IsClique s) :=
   decidable_of_iff' _ G.isClique_iff
 
-variable {G H}
+variable {G H} {a b : α}
+
+lemma isClique_empty : G.IsClique ∅ := by simp
+#align simple_graph.is_clique_empty SimpleGraph.isClique_empty
+
+lemma isClique_singleton (a : α) : G.IsClique {a} := by simp
+#align simple_graph.is_clique_singleton SimpleGraph.isClique_singleton
+
+lemma isClique_pair : G.IsClique {a, b} ↔ a ≠ b → G.Adj a b := Set.pairwise_pair_of_symmetric G.symm
+#align simple_graph.is_clique_pair SimpleGraph.isClique_pair
+
+@[simp]
+lemma isClique_insert : G.IsClique (insert a s) ↔ G.IsClique s ∧ ∀ b ∈ s, a ≠ b → G.Adj a b :=
+  Set.pairwise_insert_of_symmetric G.symm
+#align simple_graph.is_clique_insert SimpleGraph.isClique_insert
+
+lemma isClique_insert_of_not_mem (ha : a ∉ s) :
+    G.IsClique (insert a s) ↔ G.IsClique s ∧ ∀ b ∈ s, G.Adj a b :=
+  Set.pairwise_insert_of_symmetric_of_not_mem G.symm ha
+#align simple_graph.is_clique_insert_of_not_mem SimpleGraph.isClique_insert_of_not_mem
+
+lemma IsClique.insert (hs : G.IsClique s) (h : ∀ b ∈ s, a ≠ b → G.Adj a b) :
+    G.IsClique (insert a s) := hs.insert_of_symmetric G.symm h
+#align simple_graph.is_clique.insert SimpleGraph.IsClique.insert
 
-theorem IsClique.mono (h : G ≤ H) : G.IsClique s → H.IsClique s := by
-  simp_rw [isClique_iff]
-  exact Set.Pairwise.mono' h
+theorem IsClique.mono (h : G ≤ H) : G.IsClique s → H.IsClique s := Set.Pairwise.mono' h
 #align simple_graph.is_clique.mono SimpleGraph.IsClique.mono
 
-theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t := by
-  simp_rw [isClique_iff]
-  exact Set.Pairwise.mono h
+theorem IsClique.subset (h : t ⊆ s) : G.IsClique s → G.IsClique t := Set.Pairwise.mono h
 #align simple_graph.is_clique.subset SimpleGraph.IsClique.subset
 
+protected theorem IsClique.map {s : Set α} (h : G.IsClique s) {f : α ↪ β} :
+    (G.map f).IsClique (f '' s) := by
+  rintro _ ⟨a, ha, rfl⟩ _ ⟨b, hb, rfl⟩ hab
+  exact ⟨a, b, h ha hb <| ne_of_apply_ne _ hab, rfl, rfl⟩
+#align simple_graph.is_clique.map SimpleGraph.IsClique.map
+
 @[simp]
 theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Subsingleton :=
   Set.pairwise_bot_iff
@@ -111,13 +137,25 @@ instance [DecidableEq α] [DecidableRel G.Adj] {n : ℕ} {s : Finset α} :
     Decidable (G.IsNClique n s) :=
   decidable_of_iff' _ G.isNClique_iff
 
-variable {G H}
+variable {G H} {a b c : α}
+
+@[simp] lemma isNClique_empty : G.IsNClique n ∅ ↔ n = 0 := by simp [isNClique_iff, eq_comm]
+#align simple_graph.is_n_clique_empty SimpleGraph.isNClique_empty
+
+@[simp]
+lemma isNClique_singleton : G.IsNClique n {a} ↔ n = 1 := by simp [isNClique_iff, eq_comm]
+#align simple_graph.is_n_clique_singleton SimpleGraph.isNClique_singleton
 
 theorem IsNClique.mono (h : G ≤ H) : G.IsNClique n s → H.IsNClique n s := by
   simp_rw [isNClique_iff]
   exact And.imp_left (IsClique.mono h)
 #align simple_graph.is_n_clique.mono SimpleGraph.IsNClique.mono
 
+protected theorem IsNClique.map (h : G.IsNClique n s) {f : α ↪ β} :
+    (G.map f).IsNClique n (s.map f) :=
+  ⟨by rw [coe_map]; exact h.1.map, (card_map _).trans h.2⟩
+#align simple_graph.is_n_clique.map SimpleGraph.IsNClique.map
+
 @[simp]
 theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧ s.card = n := by
   rw [isNClique_iff, isClique_bot_iff]
@@ -126,7 +164,25 @@ theorem isNClique_bot_iff : (⊥ : SimpleGraph α).IsNClique n s ↔ n ≤ 1 ∧
   exact card_le_one.symm
 #align simple_graph.is_n_clique_bot_iff SimpleGraph.isNClique_bot_iff
 
-variable [DecidableEq α] {a b c : α}
+@[simp]
+theorem isNClique_zero : G.IsNClique 0 s ↔ s = ∅ := by
+  simp only [isNClique_iff, Finset.card_eq_zero, and_iff_right_iff_imp]; rintro rfl; simp
+#align simple_graph.is_n_clique_zero SimpleGraph.isNClique_zero
+
+@[simp]
+theorem isNClique_one : G.IsNClique 1 s ↔ ∃ a, s = {a} := by
+  simp only [isNClique_iff, card_eq_one, and_iff_right_iff_imp]; rintro ⟨a, rfl⟩; simp
+#align simple_graph.is_n_clique_one SimpleGraph.isNClique_one
+
+variable [DecidableEq α]
+
+theorem IsNClique.insert (hs : G.IsNClique n s) (h : ∀ b ∈ s, G.Adj a b) :
+    G.IsNClique (n + 1) (insert a s) := by
+  constructor
+  · push_cast
+    exact hs.1.insert fun b hb _ => h _ hb
+  · rw [card_insert_of_not_mem fun ha => (h _ ha).ne rfl, hs.2]
+#align simple_graph.is_n_clique.insert SimpleGraph.IsNClique.insert
 
 theorem is3Clique_triple_iff : G.IsNClique 3 {a, b, c} ↔ G.Adj a b ∧ G.Adj a c ∧ G.Adj b c := by
   simp only [isNClique_iff, isClique_iff, Set.pairwise_insert_of_symmetric G.symm, coe_insert]
@@ -207,6 +263,7 @@ theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGrap
   exact ⟨(Iso.completeGraph (Fintype.equivFin α)).symm.toEmbedding.trans f⟩
 #align simple_graph.not_clique_free_card_of_top_embedding SimpleGraph.not_cliqueFree_card_of_top_embedding
 
+@[simp]
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n := by
   intro t ht
   have := le_trans h (isNClique_bot_iff.1 ht).1
@@ -277,8 +334,87 @@ theorem cliqueFree_of_replaceVertex_cliqueFree [DecidableEq α] (s t : α) (h :
         simp_all
   · use ⟨f, hi⟩; simp_all
 
+@[simp]
+theorem cliqueFree_two : G.CliqueFree 2 ↔ G = ⊥ := by
+  classical
+  constructor
+  · simp_rw [← edgeSet_eq_empty, Set.eq_empty_iff_forall_not_mem, Sym2.forall, mem_edgeSet]
+    exact fun h a b hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.ne⟩
+  · rintro rfl
+    exact cliqueFree_bot le_rfl
+#align simple_graph.clique_free_two SimpleGraph.cliqueFree_two
+
 end CliqueFree
 
+section CliqueFreeOn
+variable {s s₁ s₂ : Set α} {t : Finset α} {a b : α} {m n : ℕ}
+
+/-- `G.CliqueFreeOn s n` means that `G` has no `n`-cliques contained in `s`. -/
+def CliqueFreeOn (G : SimpleGraph α) (s : Set α) (n : ℕ) : Prop :=
+  ∀ ⦃t⦄, ↑t ⊆ s → ¬G.IsNClique n t
+#align simple_graph.clique_free_on SimpleGraph.CliqueFreeOn
+
+theorem CliqueFreeOn.subset (hs : s₁ ⊆ s₂) (h₂ : G.CliqueFreeOn s₂ n) : G.CliqueFreeOn s₁ n :=
+  fun _t hts => h₂ <| hts.trans hs
+#align simple_graph.clique_free_on.subset SimpleGraph.CliqueFreeOn.subset
+
+theorem CliqueFreeOn.mono (hmn : m ≤ n) (hG : G.CliqueFreeOn s m) : G.CliqueFreeOn s n := by
+  rintro t hts ht
+  obtain ⟨u, hut, hu⟩ := t.exists_smaller_set _ (hmn.trans ht.card_eq.ge)
+  exact hG ((coe_subset.2 hut).trans hts) ⟨ht.clique.subset hut, hu⟩
+#align simple_graph.clique_free_on.mono SimpleGraph.CliqueFreeOn.mono
+
+theorem CliqueFreeOn.anti (hGH : G ≤ H) (hH : H.CliqueFreeOn s n) : G.CliqueFreeOn s n :=
+  fun _t hts ht => hH hts <| ht.mono hGH
+#align simple_graph.clique_free_on.anti SimpleGraph.CliqueFreeOn.anti
+
+@[simp]
+theorem cliqueFreeOn_empty : G.CliqueFreeOn ∅ n ↔ n ≠ 0 := by
+  simp [CliqueFreeOn, Set.subset_empty_iff]
+#align simple_graph.clique_free_on_empty SimpleGraph.cliqueFreeOn_empty
+
+@[simp]
+theorem cliqueFreeOn_singleton : G.CliqueFreeOn {a} n ↔ 1 < n := by
+  obtain _ | _ | n := n <;>
+    simp [CliqueFreeOn, isNClique_iff, ← subset_singleton_iff', (Nat.succ_ne_zero _).symm]
+#align simple_graph.clique_free_on_singleton SimpleGraph.cliqueFreeOn_singleton
+
+@[simp]
+theorem cliqueFreeOn_univ : G.CliqueFreeOn Set.univ n ↔ G.CliqueFree n := by
+  simp [CliqueFree, CliqueFreeOn]
+#align simple_graph.clique_free_on_univ SimpleGraph.cliqueFreeOn_univ
+
+protected theorem CliqueFree.cliqueFreeOn (hG : G.CliqueFree n) : G.CliqueFreeOn s n :=
+  fun _t _ ↦ hG _
+#align simple_graph.clique_free.clique_free_on SimpleGraph.CliqueFree.cliqueFreeOn
+
+theorem cliqueFreeOn_of_card_lt {s : Finset α} (h : s.card < n) : G.CliqueFreeOn s n :=
+  fun _t hts ht => h.not_le <| ht.2.symm.trans_le <| card_mono hts
+#align simple_graph.clique_free_on_of_card_lt SimpleGraph.cliqueFreeOn_of_card_lt
+
+-- TODO: Restate using `SimpleGraph.IndepSet` once we have it
+@[simp]
+theorem cliqueFreeOn_two : G.CliqueFreeOn s 2 ↔ s.Pairwise (G.Adjᶜ) := by
+  classical
+  refine' ⟨fun h a ha b hb _ hab => h _ ⟨by simpa [hab.ne], card_doubleton hab.ne⟩, _⟩
+  · push_cast
+    exact Set.insert_subset_iff.2 ⟨ha, Set.singleton_subset_iff.2 hb⟩
+  simp only [CliqueFreeOn, isNClique_iff, card_eq_two, coe_subset, not_and, not_exists]
+  rintro h t hst ht a b hab rfl
+  simp only [coe_insert, coe_singleton, Set.insert_subset_iff, Set.singleton_subset_iff] at hst
+  refine' h hst.1 hst.2 hab (ht _ _ hab) <;> simp
+#align simple_graph.clique_free_on_two SimpleGraph.cliqueFreeOn_two
+
+theorem CliqueFreeOn.of_succ (hs : G.CliqueFreeOn s (n + 1)) (ha : a ∈ s) :
+    G.CliqueFreeOn (s ∩ G.neighborSet a) n := by
+  classical
+  refine' fun t hts ht => hs _ (ht.insert fun b hb => (hts hb).2)
+  push_cast
+  exact Set.insert_subset_iff.2 ⟨ha, hts.trans <| Set.inter_subset_left _ _⟩
+#align simple_graph.clique_free_on.of_succ SimpleGraph.CliqueFreeOn.of_succ
+
+end CliqueFreeOn
+
 /-! ### Set of cliques -/
 
 
@@ -291,6 +427,9 @@ def cliqueSet (n : ℕ) : Set (Finset α) :=
   { s | G.IsNClique n s }
 #align simple_graph.clique_set SimpleGraph.cliqueSet
 
+variable {G H}
+
+@[simp]
 theorem mem_cliqueSet_iff : s ∈ G.cliqueSet n ↔ G.IsNClique n s :=
   Iff.rfl
 #align simple_graph.mem_clique_set_iff SimpleGraph.mem_cliqueSet_iff
@@ -300,13 +439,9 @@ theorem cliqueSet_eq_empty_iff : G.cliqueSet n = ∅ ↔ G.CliqueFree n := by
   simp_rw [CliqueFree, Set.eq_empty_iff_forall_not_mem, mem_cliqueSet_iff]
 #align simple_graph.clique_set_eq_empty_iff SimpleGraph.cliqueSet_eq_empty_iff
 
-alias ⟨_, CliqueFree.cliqueSet⟩ := cliqueSet_eq_empty_iff
+protected alias ⟨_, CliqueFree.cliqueSet⟩ := cliqueSet_eq_empty_iff
 #align simple_graph.clique_free.clique_set SimpleGraph.CliqueFree.cliqueSet
 
---attribute [protected] CliqueFree.cliqueSet -- porting note: removed
-
-variable {G H}
-
 @[mono]
 theorem cliqueSet_mono (h : G ≤ H) : G.cliqueSet n ⊆ H.cliqueSet n :=
   fun _ ↦ IsNClique.mono h
@@ -316,6 +451,49 @@ theorem cliqueSet_mono' (h : G ≤ H) : G.cliqueSet ≤ H.cliqueSet :=
   fun _ ↦ cliqueSet_mono h
 #align simple_graph.clique_set_mono' SimpleGraph.cliqueSet_mono'
 
+@[simp]
+theorem cliqueSet_zero (G : SimpleGraph α) : G.cliqueSet 0 = {∅} := Set.ext fun s => by simp
+#align simple_graph.clique_set_zero SimpleGraph.cliqueSet_zero
+
+@[simp]
+theorem cliqueSet_one (G : SimpleGraph α) : G.cliqueSet 1 = Set.range singleton :=
+  Set.ext fun s => by simp [eq_comm]
+#align simple_graph.clique_set_one SimpleGraph.cliqueSet_one
+
+@[simp]
+theorem cliqueSet_bot (hn : 1 < n) : (⊥ : SimpleGraph α).cliqueSet n = ∅ :=
+  (cliqueFree_bot hn).cliqueSet
+#align simple_graph.clique_set_bot SimpleGraph.cliqueSet_bot
+
+@[simp]
+theorem cliqueSet_map (hn : n ≠ 1) (G : SimpleGraph α) (f : α ↪ β) :
+    (G.map f).cliqueSet n = map f '' G.cliqueSet n := by
+  ext s
+  constructor
+  · rintro ⟨hs, rfl⟩
+    have hs' : (s.preimage f <| f.injective.injOn _).map f = s := by
+      classical
+      rw [map_eq_image, image_preimage, filter_true_of_mem]
+      rintro a ha
+      obtain ⟨b, hb, hba⟩ := exists_mem_ne (hn.lt_of_le' <| Finset.card_pos.2 ⟨a, ha⟩) a
+      obtain ⟨c, _, _, hc, _⟩ := hs ha hb hba.symm
+      exact ⟨c, hc⟩
+    refine' ⟨s.preimage f <| f.injective.injOn _, ⟨_, by rw [← card_map f, hs']⟩, hs'⟩
+    rw [coe_preimage]
+    exact fun a ha b hb hab => map_adj_apply.1 (hs ha hb <| f.injective.ne hab)
+  · rintro ⟨s, hs, rfl⟩
+    exact hs.map
+#align simple_graph.clique_set_map SimpleGraph.cliqueSet_map
+
+@[simp]
+theorem cliqueSet_map_of_equiv (G : SimpleGraph α) (e : α ≃ β) (n : ℕ) :
+    (G.map e.toEmbedding).cliqueSet n = map e.toEmbedding '' G.cliqueSet n := by
+  obtain rfl | hn := eq_or_ne n 1
+  · ext
+    simp [e.exists_congr_left]
+  · exact cliqueSet_map hn _ _
+#align simple_graph.clique_set_map_of_equiv SimpleGraph.cliqueSet_map_of_equiv
+
 end CliqueSet
 
 /-! ### Finset of cliques -/
@@ -330,32 +508,56 @@ def cliqueFinset (n : ℕ) : Finset (Finset α) :=
   univ.filter <| G.IsNClique n
 #align simple_graph.clique_finset SimpleGraph.cliqueFinset
 
+variable {G} in
+@[simp]
 theorem mem_cliqueFinset_iff : s ∈ G.cliqueFinset n ↔ G.IsNClique n s :=
   mem_filter.trans <| and_iff_right <| mem_univ _
 #align simple_graph.mem_clique_finset_iff SimpleGraph.mem_cliqueFinset_iff
 
-@[simp]
+@[simp, norm_cast]
 theorem coe_cliqueFinset (n : ℕ) : (G.cliqueFinset n : Set (Finset α)) = G.cliqueSet n :=
-  Set.ext fun _ ↦ mem_cliqueFinset_iff _
+  Set.ext fun _ ↦ mem_cliqueFinset_iff
 #align simple_graph.coe_clique_finset SimpleGraph.coe_cliqueFinset
 
+variable {G}
+
 @[simp]
 theorem cliqueFinset_eq_empty_iff : G.cliqueFinset n = ∅ ↔ G.CliqueFree n := by
   simp_rw [CliqueFree, eq_empty_iff_forall_not_mem, mem_cliqueFinset_iff]
 #align simple_graph.clique_finset_eq_empty_iff SimpleGraph.cliqueFinset_eq_empty_iff
 
-alias ⟨_, CliqueFree.cliqueFinset⟩ := cliqueFinset_eq_empty_iff
+protected alias ⟨_, CliqueFree.cliqueFinset⟩ := cliqueFinset_eq_empty_iff
 #align simple_graph.clique_free.clique_finset SimpleGraph.CliqueFree.cliqueFinset
 
---attribute [protected] CliqueFree.cliqueFinset -- porting note: removed
+theorem card_cliqueFinset_le : (G.cliqueFinset n).card ≤ (card α).choose n := by
+  rw [← card_univ, ← card_powersetCard]
+  refine' card_mono fun s => _
+  simpa [mem_powersetCard_univ] using IsNClique.card_eq
+#align simple_graph.card_clique_finset_le SimpleGraph.card_cliqueFinset_le
 
-variable {G} [DecidableRel H.Adj]
+variable [DecidableRel H.Adj]
 
 @[mono]
 theorem cliqueFinset_mono (h : G ≤ H) : G.cliqueFinset n ⊆ H.cliqueFinset n :=
   monotone_filter_right _ fun _ ↦ IsNClique.mono h
 #align simple_graph.clique_finset_mono SimpleGraph.cliqueFinset_mono
 
+variable [Fintype β] [DecidableEq β] (G)
+
+@[simp]
+theorem cliqueFinset_map (f : α ↪ β) (hn : n ≠ 1) :
+    (G.map f).cliqueFinset n = (G.cliqueFinset n).map ⟨map f, Finset.map_injective _⟩ :=
+  coe_injective <| by
+    simp_rw [coe_cliqueFinset, cliqueSet_map hn, coe_map, coe_cliqueFinset, Embedding.coeFn_mk]
+#align simple_graph.clique_finset_map SimpleGraph.cliqueFinset_map
+
+@[simp]
+theorem cliqueFinset_map_of_equiv (e : α ≃ β) (n : ℕ) :
+    (G.map e.toEmbedding).cliqueFinset n =
+      (G.cliqueFinset n).map ⟨map e.toEmbedding, Finset.map_injective _⟩ :=
+  coe_injective <| by push_cast; exact cliqueSet_map_of_equiv _ _ _
+#align simple_graph.clique_finset_map_of_equiv SimpleGraph.cliqueFinset_map_of_equiv
+
 end CliqueFinset
 
 end SimpleGraph

chore: bump to v4.3.0-rc2 (#8366)

PR contents

This is the supremum of

#8284
#8056
#8023
#8332
#8226 (already approved)
#7834 (already approved)

along with some minor fixes from failures on nightly-testing as Mathlib master is merged into it.

Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.

I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0 branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

leanprover/lean4#2778

We can get rid of all the

local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)

macros across Mathlib (and in any projects that want to write natural number powers of reals).

leanprover/lean4#2722

Changes the default behaviour of simp to (config := {decide := false}). This makes simp (and consequentially norm_num) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp or norm_num to decide or rfl, or adding (config := {decide := true}).

leanprover/lean4#2783

This changed the behaviour of simp so that simp [f] will only unfold "fully applied" occurrences of f. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true }). We may in future add a syntax for this, e.g. simp [!f]; please provide feedback! In the meantime, we have made the following changes:

switching to using explicit lemmas that have the intended level of application
(config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
Using @[eqns] to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp and Function.flip.

This change in Lean may require further changes down the line (e.g. adding the !f syntax, and/or upstreaming the special treatment for Function.comp and Function.flip, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>

40b64f79

Diff

@@ -210,7 +210,7 @@ theorem not_cliqueFree_card_of_top_embedding [Fintype α] (f : (⊤ : SimpleGrap
 theorem cliqueFree_bot (h : 2 ≤ n) : (⊥ : SimpleGraph α).CliqueFree n := by
   intro t ht
   have := le_trans h (isNClique_bot_iff.1 ht).1
-  simp only at this
+  contradiction
 #align simple_graph.clique_free_bot SimpleGraph.cliqueFree_bot
 
 theorem CliqueFree.mono (h : m ≤ n) : G.CliqueFree m → G.CliqueFree n := by

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

5f84b04f

Diff

@@ -226,7 +226,7 @@ theorem CliqueFree.anti (h : G ≤ H) : H.CliqueFree n → G.CliqueFree n :=
 /-- See `SimpleGraph.cliqueFree_of_chromaticNumber_lt` for a tighter bound. -/
 theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n := by
   by_contra h
-  refine' Nat.lt_le_antisymm hc _
+  refine' Nat.lt_le_asymm hc _
   rw [cliqueFree_iff, not_isEmpty_iff] at h
   simpa only [Fintype.card_fin] using Fintype.card_le_of_embedding h.some.toEmbedding
 #align simple_graph.clique_free_of_card_lt SimpleGraph.cliqueFree_of_card_lt

chore: Fix name of SimpleGraph.Adj projection (#8179)

simps was generating lemmas named _Adj. This PR makes it generate _adj instead, to follow the naming convention.

2fd9651c

Diff

@@ -56,7 +56,7 @@ theorem isClique_iff_induce_eq : G.IsClique s ↔ G.induce s = ⊤ := by
   constructor
   · intro h
     ext ⟨v, hv⟩ ⟨w, hw⟩
-    simp only [comap_Adj, Subtype.coe_mk, top_adj, Ne.def, Subtype.mk_eq_mk]
+    simp only [comap_adj, Subtype.coe_mk, top_adj, Ne.def, Subtype.mk_eq_mk]
     exact ⟨Adj.ne, h hv hw⟩
   · intro h v hv w hw hne
     have h2 : (G.induce s).Adj ⟨v, hv⟩ ⟨w, hw⟩ = _ := rfl
@@ -173,7 +173,7 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   simp only [coe_map, Set.mem_image, coe_univ, Set.mem_univ, true_and_iff] at hv hw
   obtain ⟨v', rfl⟩ := hv
   obtain ⟨w', rfl⟩ := hw
-  simp only [coe_sort_coe, RelEmbedding.coe_toEmbedding, comap_Adj, Function.Embedding.coe_subtype,
+  simp only [coe_sort_coe, RelEmbedding.coe_toEmbedding, comap_adj, Function.Embedding.coe_subtype,
     f.map_adj_iff, top_adj, ne_eq, Subtype.mk.injEq, RelEmbedding.inj]
   -- This used to be the end of the proof before leanprover/lean4#2644
   erw [Function.Embedding.coe_subtype, f.map_adj_iff]
@@ -237,7 +237,7 @@ theorem cliqueFree_completeMultipartiteGraph {ι : Type*} [Fintype ι] (V : ι 
   rw [cliqueFree_iff, isEmpty_iff]
   intro f
   obtain ⟨v, w, hn, he⟩ := exists_ne_map_eq_of_card_lt (Sigma.fst ∘ f) (by simp [hc])
-  rw [← top_adj, ← f.map_adj_iff, comap_Adj, top_adj] at hn
+  rw [← top_adj, ← f.map_adj_iff, comap_adj, top_adj] at hn
   exact absurd he hn
 
 /-- Clique-freeness is preserved by `replaceVertex`. -/

Revert "chore: revert #7703 (#7710)"

This reverts commit f3695eb2.

ab56fa28

Diff

@@ -175,6 +175,9 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   obtain ⟨w', rfl⟩ := hw
   simp only [coe_sort_coe, RelEmbedding.coe_toEmbedding, comap_Adj, Function.Embedding.coe_subtype,
     f.map_adj_iff, top_adj, ne_eq, Subtype.mk.injEq, RelEmbedding.inj]
+  -- This used to be the end of the proof before leanprover/lean4#2644
+  erw [Function.Embedding.coe_subtype, f.map_adj_iff]
+  simp
 #align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embedding
 
 /-- An embedding of a complete graph that witnesses the fact that the graph is not clique-free. -/

chore: revert #7703 (#7710)

This reverts commit 26eb2b0a.

f3695eb2

Diff

@@ -175,9 +175,6 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   obtain ⟨w', rfl⟩ := hw
   simp only [coe_sort_coe, RelEmbedding.coe_toEmbedding, comap_Adj, Function.Embedding.coe_subtype,
     f.map_adj_iff, top_adj, ne_eq, Subtype.mk.injEq, RelEmbedding.inj]
-  -- This used to be the end of the proof before leanprover/lean4#2644
-  erw [Function.Embedding.coe_subtype, f.map_adj_iff]
-  simp
 #align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embedding
 
 /-- An embedding of a complete graph that witnesses the fact that the graph is not clique-free. -/

chore: bump toolchain to v4.2.0-rc2 (#7703)

This includes all the changes from #7606.

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

26eb2b0a

Diff

@@ -175,6 +175,9 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   obtain ⟨w', rfl⟩ := hw
   simp only [coe_sort_coe, RelEmbedding.coe_toEmbedding, comap_Adj, Function.Embedding.coe_subtype,
     f.map_adj_iff, top_adj, ne_eq, Subtype.mk.injEq, RelEmbedding.inj]
+  -- This used to be the end of the proof before leanprover/lean4#2644
+  erw [Function.Embedding.coe_subtype, f.map_adj_iff]
+  simp
 #align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embedding
 
 /-- An embedding of a complete graph that witnesses the fact that the graph is not clique-free. -/

feat: vertex replacement (#6808)

cliqueFree_of_replaceVertex_cliqueFree is still quite long.

6c63dfbe

Diff

@@ -237,6 +237,43 @@ theorem cliqueFree_completeMultipartiteGraph {ι : Type*} [Fintype ι] (V : ι 
   rw [← top_adj, ← f.map_adj_iff, comap_Adj, top_adj] at hn
   exact absurd he hn
 
+/-- Clique-freeness is preserved by `replaceVertex`. -/
+theorem cliqueFree_of_replaceVertex_cliqueFree [DecidableEq α] (s t : α) (h : G.CliqueFree n) :
+    (G.replaceVertex s t).CliqueFree n := by
+  contrapose h
+  obtain ⟨⟨f, hi⟩, ha⟩ := topEmbeddingOfNotCliqueFree h
+  simp only [Function.Embedding.coeFn_mk, top_adj, ne_eq] at ha
+  rw [not_cliqueFree_iff]
+  by_cases mt : t ∈ Set.range f
+  · obtain ⟨x, hx⟩ := mt
+    by_cases ms : s ∈ Set.range f
+    · obtain ⟨y, hy⟩ := ms
+      by_cases hst : s = t
+      · simp_all [not_cliqueFree_iff]
+      · replace ha := @ha x y; simp_all
+    · use ⟨fun v => if v = x then s else f v, ?_⟩
+      swap
+      · intro a b
+        dsimp only
+        split_ifs
+        · simp_all
+        · intro; simp_all
+        · intro; simp_all
+        · apply hi
+      intro a b
+      simp only [Function.Embedding.coeFn_mk, top_adj, ne_eq]
+      split_ifs with h1 h2 h2
+      · simp_all
+      · have := (@ha b x).mpr h2
+        split_ifs at this; subst h1; tauto
+      · have := (@ha a x).mpr h1
+        split_ifs at this; subst h2; tauto
+      · rw [← @ha a b]
+        have := (@hi a x).mt h1
+        have := (@hi b x).mt h2
+        simp_all
+  · use ⟨f, hi⟩; simp_all
+
 end CliqueFree
 
 /-! ### Set of cliques -/

https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Complete.20multipartite.20graphs/near/386500598

feat: complete multipartite graphs (#6762)

5d955e02

Diff

@@ -153,7 +153,7 @@ section CliqueFree
 
 variable {m n : ℕ}
 
-/-- `G.clique_free n` means that `G` has no `n`-cliques. -/
+/-- `G.CliqueFree n` means that `G` has no `n`-cliques. -/
 def CliqueFree (n : ℕ) : Prop :=
   ∀ t, ¬G.IsNClique n t
 #align simple_graph.clique_free SimpleGraph.CliqueFree
@@ -220,7 +220,7 @@ theorem CliqueFree.anti (h : G ≤ H) : H.CliqueFree n → G.CliqueFree n :=
   forall_imp fun _ ↦ mt <| IsNClique.mono h
 #align simple_graph.clique_free.anti SimpleGraph.CliqueFree.anti
 
-/-- See `simple_graph.clique_free_chromatic_number_succ` for a tighter bound. -/
+/-- See `SimpleGraph.cliqueFree_of_chromaticNumber_lt` for a tighter bound. -/
 theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n := by
   by_contra h
   refine' Nat.lt_le_antisymm hc _
@@ -228,6 +228,15 @@ theorem cliqueFree_of_card_lt [Fintype α] (hc : card α < n) : G.CliqueFree n :
   simpa only [Fintype.card_fin] using Fintype.card_le_of_embedding h.some.toEmbedding
 #align simple_graph.clique_free_of_card_lt SimpleGraph.cliqueFree_of_card_lt
 
+/-- A complete `r`-partite graph has no `n`-cliques for `r < n`. -/
+theorem cliqueFree_completeMultipartiteGraph {ι : Type*} [Fintype ι] (V : ι → Type*)
+    (hc : card ι < n) : (completeMultipartiteGraph V).CliqueFree n := by
+  rw [cliqueFree_iff, isEmpty_iff]
+  intro f
+  obtain ⟨v, w, hn, he⟩ := exists_ne_map_eq_of_card_lt (Sigma.fst ∘ f) (by simp [hc])
+  rw [← top_adj, ← f.map_adj_iff, comap_Adj, top_adj] at hn
+  exact absurd he hn
+
 end CliqueFree
 
 /-! ### Set of cliques -/

feat: patch for new alias command (#6172)

19e0ba92

Diff

@@ -85,7 +85,7 @@ theorem isClique_bot_iff : (⊥ : SimpleGraph α).IsClique s ↔ (s : Set α).Su
   Set.pairwise_bot_iff
 #align simple_graph.is_clique_bot_iff SimpleGraph.isClique_bot_iff
 
-alias isClique_bot_iff ↔ IsClique.subsingleton _
+alias ⟨IsClique.subsingleton, _⟩ := isClique_bot_iff
 #align simple_graph.is_clique.subsingleton SimpleGraph.IsClique.subsingleton
 
 end Clique
@@ -251,7 +251,7 @@ theorem cliqueSet_eq_empty_iff : G.cliqueSet n = ∅ ↔ G.CliqueFree n := by
   simp_rw [CliqueFree, Set.eq_empty_iff_forall_not_mem, mem_cliqueSet_iff]
 #align simple_graph.clique_set_eq_empty_iff SimpleGraph.cliqueSet_eq_empty_iff
 
-alias cliqueSet_eq_empty_iff ↔ _ CliqueFree.cliqueSet
+alias ⟨_, CliqueFree.cliqueSet⟩ := cliqueSet_eq_empty_iff
 #align simple_graph.clique_free.clique_set SimpleGraph.CliqueFree.cliqueSet
 
 --attribute [protected] CliqueFree.cliqueSet -- porting note: removed
@@ -295,7 +295,7 @@ theorem cliqueFinset_eq_empty_iff : G.cliqueFinset n = ∅ ↔ G.CliqueFree n :=
   simp_rw [CliqueFree, eq_empty_iff_forall_not_mem, mem_cliqueFinset_iff]
 #align simple_graph.clique_finset_eq_empty_iff SimpleGraph.cliqueFinset_eq_empty_iff
 
-alias cliqueFinset_eq_empty_iff ↔ _ CliqueFree.cliqueFinset
+alias ⟨_, CliqueFree.cliqueFinset⟩ := cliqueFinset_eq_empty_iff
 #align simple_graph.clique_free.clique_finset SimpleGraph.CliqueFree.cliqueFinset
 
 --attribute [protected] CliqueFree.cliqueFinset -- porting note: removed

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

@@ -32,7 +32,7 @@ open Finset Fintype
 
 namespace SimpleGraph
 
-variable {α : Type _} (G H : SimpleGraph α)
+variable {α : Type*} (G H : SimpleGraph α)
 
 /-! ### Cliques -/

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,15 +2,12 @@
 Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies, Bhavik Mehta
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.clique
-! leanprover-community/mathlib commit cd7f0626a0b04be1dda223a26123313514a55fb4
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Combinatorics.SimpleGraph.Basic
 import Mathlib.Data.Finset.Pairwise
 
+#align_import combinatorics.simple_graph.clique from "leanprover-community/mathlib"@"cd7f0626a0b04be1dda223a26123313514a55fb4"
+
 /-!
 # Graph cliques

chore: fix grammar in docs (#5668)

15cdb8ec

Diff

@@ -20,7 +20,7 @@ adjacent.
 ## Main declarations
 
 * `SimpleGraph.IsClique`: Predicate for a set of vertices to be a clique.
-* `SimpleGraph.IsNClique`: Predicate for a set of vertices to be a `n`-clique.
+* `SimpleGraph.IsNClique`: Predicate for a set of vertices to be an `n`-clique.
 * `SimpleGraph.cliqueFinset`: Finset of `n`-cliques of a graph.
 * `SimpleGraph.CliqueFree`: Predicate for a graph to have no `n`-cliques.
 
@@ -100,7 +100,7 @@ section NClique
 
 variable {n : ℕ} {s : Finset α}
 
-/-- A `n`-clique in a graph is a set of `n` vertices which are pairwise connected. -/
+/-- An `n`-clique in a graph is a set of `n` vertices which are pairwise connected. -/
 structure IsNClique (n : ℕ) (s : Finset α) : Prop where
   clique : G.IsClique s
   card_eq : s.card = n

chore: use FunLike.coe as coercion for OrderIso and RelEmbedding (#3082)

The changes I made were.

Use FunLike.coe instead of the previous definition for the coercion from RelEmbedding To functions and OrderIso to functions. The previous definition was

instance : CoeFun (r ↪r s) fun _ => α → β :=
--   ⟨fun o => o.toEmbedding⟩

This does not display nicely.

I also restored the simp attributes on a few lemmas that had their simp attributes removed during the port. Eventually we might want a RelEmbeddingLike class, but this PR does not implement that.

I also added a few lemmas that proved that coercions to function commute with RelEmbedding.toRelHom or similar.

The other changes are just fixing the build. One strange issue is that the lemma Finset.mapEmbedding_apply seems to be harder to use, it has to be used with rw instead of simp

Co-authored-by: Chris Hughes <33847686+ChrisHughes24@users.noreply.github.com>

c8b10b06

Diff

@@ -176,9 +176,8 @@ theorem not_cliqueFree_of_top_embedding {n : ℕ} (f : (⊤ : SimpleGraph (Fin n
   simp only [coe_map, Set.mem_image, coe_univ, Set.mem_univ, true_and_iff] at hv hw
   obtain ⟨v', rfl⟩ := hv
   obtain ⟨w', rfl⟩ := hw
-  simp only [f.map_adj_iff, comap_Adj, Function.Embedding.coe_subtype, top_adj, Ne.def,
-    Subtype.mk_eq_mk]
-  exact (Function.Embedding.apply_eq_iff_eq _ _ _).symm.not
+  simp only [coe_sort_coe, RelEmbedding.coe_toEmbedding, comap_Adj, Function.Embedding.coe_subtype,
+    f.map_adj_iff, top_adj, ne_eq, Subtype.mk.injEq, RelEmbedding.inj]
 #align simple_graph.not_clique_free_of_top_embedding SimpleGraph.not_cliqueFree_of_top_embedding
 
 /-- An embedding of a complete graph that witnesses the fact that the graph is not clique-free. -/

feat: improvements to congr! and convert (#2606)

There is now configuration for congr!, convert, and convert_to to control parts of the congruence algorithm, in particular transparency settings when applying congruence lemmas.
congr! now applies congruence lemmas with reducible transparency by default. This prevents it from unfolding definitions when applying congruence lemmas. It also now tries both the LHS-biased and RHS-biased simp congruence lemmas, with a configuration option to set which it should try first.
There is now a new HEq congruence lemma generator that gives each hypothesis access to the proofs of previous hypotheses. This means that if you have an equality ⊢ ⟨a, x⟩ = ⟨b, y⟩ of sigma types, congr! turns this into goals ⊢ a = b and ⊢ a = b → HEq x y (note that congr! will also auto-introduce a = b for you in the second goal). This congruence lemma generator applies to more cases than the simp congruence lemma generator does.
congr! (and hence convert) are more careful about applying lemmas that don't force definitions to unfold. There were a number of cases in mathlib where the implementation of congr was being abused to unfold definitions.
With set_option trace.congr! true you can see what congr! sees when it is deciding on congruence lemmas.
There is also a bug fix in convert_to to do using 1 when there is no using clause, to match its documentation.

Note that congr! is more capable than congr at finding a way to equate left-hand sides and right-hand sides, so you will frequently need to limit its depth with a using clause. However, there is also a new heuristic to prevent considering unlikely-to-be-provable type equalities (controlled by the typeEqs option), which can help limit the depth automatically.

There is also a predefined configuration that you can invoke with, for example, convert (config := .unfoldSameFun) h, that causes it to behave more like congr, including using default transparency when unfolding.

61ca0ea8

Diff

@@ -190,7 +190,8 @@ noncomputable def topEmbeddingOfNotCliqueFree {n : ℕ} (h : ¬G.CliqueFree n) :
     apply Iso.completeGraph
     simpa using (Fintype.equivFin h.choose).symm
   rw [← ha] at this
-  convert (Embedding.induce ↑h.choose.toSet).comp this.toEmbedding <;> exact hb.symm
+  convert (Embedding.induce ↑h.choose.toSet).comp this.toEmbedding
+  exact hb.symm
 #align simple_graph.top_embedding_of_not_clique_free SimpleGraph.topEmbeddingOfNotCliqueFree
 
 theorem not_cliqueFree_iff (n : ℕ) : ¬G.CliqueFree n ↔ Nonempty ((⊤ : SimpleGraph (Fin n)) ↪g G) :=