uniquely_clique_saturated_vertex_deleted_of_universal
Let r ≥ 3 be an integer, and let G be a finite simple graph. If G is uniquely K_r-saturated and x is a universal vertex of G, then the vertex-deleted subgraph G - x is uniquely K_{r-1}-saturated.
Statement
theorem uniquely_clique_saturated_vertex_deleted_of_universal {V : Type*} [Fintype V] (G : SimpleGraph V) {r : ℕ} (hr : 3 ≤ r) (hG : is_uniquely_clique_saturated G r) (x : V) (hx : G.IsUniversal x) : is_uniquely_clique_saturated (G.induce (Set.univ \ {x})) (r - 1)
- Source
- arXiv:2611.13656 Proposition 2.1 (i)
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_uniquely_clique_saturatedA simple graph G is uniquely K_r-saturated if it contains no clique of size r, but adding any non-edge e to G creates exactly one clique…
- Used by 1
- uniquely_clique_saturated_universal_and_coneLet r ≥ 3 be an integer, and let G be a finite simple graph. If G is uniquely K_r-saturated, then (i) for every universal vertex x of G,…
Read back from the Lean
For any finite type $V$, any simple graph $G$ on $V$, any natural number $r$ such that $3 \le r$, if $G$ is uniquely $r$-clique saturated (is_uniquely_clique_saturated G r), and $x \in V$ is a universal vertex of $G$ (G.IsUniversal x), then the induced subgraph of $G$ on the vertices different from $x$ (the subtype Set.univ \ {x}) is uniquely $(r - 1)$-clique saturated (is_uniquely_clique_saturated (G.induce (Set.univ \ {x})) (r - 1)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes that G - x is uniquely K_{r-1}-saturated by relating cliques in G - x to cliques in G via the universal vertex x. First, G - x cannot contain an (r-1)-clique, because adjoining x (which is adjacent to all other vertices) would produce an r-clique in G, contradicting that G is K_r-free. Second, adding any non-edge e = {a, b} to G - x corresponds to adding it to G, creating a unique r-clique S in G + e. This clique S must contain x—otherwise replacing an element of S with x would yield a second r-clique—and therefore S \ {x} is the unique (r-1)-clique created in (G - x) + e.
To show that G - x is uniquely K_{r-1}-saturated, it suffices to show that G - x contains no (r-1)-clique and that adding any non-edge to G - x creates a unique (r-1)-clique.
Unfold the definition of uniquely clique-saturated (`is_uniquely_clique_saturated`) for both G and the induced subgraph G - x. This yields the assumptions that G has no r-clique (`hno`) and that adding any non-edge to G produces a unique r-clique (`huniq`). Set up the canonical inclusion embedding φ from V \ {x} into V, observe (`hanx`) that no vertex in the domain equals x, and split the goal into the two conditions for unique saturation.
uses
is_uniquely_clique_saturated,Function.Embedding.subtypeclassical rw [is_uniquely_clique_saturated] at hG ⊢ obtain ⟨hno, huniq⟩ := hG let φ : ↥(Set.univ \ ({x} : Set V)) ↪ V := Function.Embedding.subtype (fun v => v ∈ (Set.univ \ ({x} : Set V))) have hanx : ∀ (a : ↥(Set.univ \ ({x} : Set V))), (a:V) ≠ x := fun a => by simpa using a.property.2 constructor
The vertex-deleted subgraph G - x contains no (r-1)-clique.
Suppose, for contradiction, that s is an (r-1)-clique in G - x. The embedding φ maps s to a clique of size r - 1 in G. Since every vertex of s is distinct from x, x ∉ φ(s). Because x is universal in G, x is adjacent to every vertex of φ(s), so inserting x yields a clique φ(s) ∪ {x} in G of size (r - 1) + 1 = r. This is an r-clique in G, contradicting the assumption (`hno`) that G contains no r-clique.
uses
SimpleGraph.isNClique_iff,SimpleGraph.IsClique.map,SimpleGraph.map_adj,SimpleGraph.induce_adj,SimpleGraph.IsClique.mono,Finset.coe_map,Finset.mem_map,Finset.card_map,Finset.coe_insert,SimpleGraph.isClique_insert,Finset.card_insert_of_notMem· intro s hs rw [SimpleGraph.isNClique_iff] at hs obtain ⟨hclique, hcard⟩ := hs have h1 : (SimpleGraph.map (⇑φ) (G.induce (Set.univ \ ({x} : Set V)))).IsClique (⇑φ '' ↑s) := SimpleGraph.IsClique.map hclique (f := φ) have hle : SimpleGraph.map (⇑φ) (G.induce (Set.univ \ ({x} : Set V))) ≤ G := by intro a b hab rw [SimpleGraph.map_adj] at hab obtain ⟨a', b', hadj, ha, hb⟩ := hab rw [← ha, ← hb] exact (SimpleGraph.induce_adj).mp hadj have h2 : G.IsClique (⇑φ '' ↑s) := SimpleGraph.IsClique.mono hle h1 rw [← Finset.coe_map] at h2 have hxnotmem : x ∉ s.map φ := by rw [Finset.mem_map] rintro ⟨a, ha, hax⟩ exact (hanx a) hax have hcard' : (s.map φ).card = r - 1 := by rw [Finset.card_map, hcard] have h3 : G.IsClique (↑(insert x (s.map φ)) : Set V) := by rw [Finset.coe_insert] rw [SimpleGraph.isClique_insert] refine ⟨h2, ?_⟩ intro b hb hxb exact hx hxb have h4 : (insert x (s.map φ)).card = r := by rw [Finset.card_insert_of_notMem hxnotmem, hcard'] omega exact hno _ (by rw [SimpleGraph.isNClique_iff]; exact ⟨h3, h4⟩)
Any non-edge {a, b} of G - x is also a non-edge of G, and adding it to G creates a unique r-clique S in G + ab.
Let e = {a, b} be a non-edge of G - x with a ≠ b. Since G - x is an induced subgraph, non-adjacency in G - x implies that a and b are non-adjacent in G. Thus {a, b} is a non-edge of G. By the unique saturation of G (`huniq`), adding the edge {a, b} to G creates a unique r-clique S in G + ab.
uses
Sym2.ind,SimpleGraph.mem_edgeSet,SimpleGraph.compl_adj,SimpleGraph.induce_adj,SimpleGraph.isNClique_iff· intro e induction e using Sym2.ind with | _ a b => intro hab rw [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj] at hab obtain ⟨habne, habnotadj⟩ := hab have hGnotadj : ¬ G.Adj (a:V) (b:V) := by simpa only [SimpleGraph.induce_adj] using habnotadj have hne' : (a:V) ≠ (b:V) := fun h => habne (φ.injective h) have he' : s((a:V),(b:V)) ∈ Gᶜ.edgeSet := by rw [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj] exact ⟨hne', hGnotadj⟩ obtain ⟨S, hS, hSuniq⟩ := huniq _ he' rw [SimpleGraph.isNClique_iff] at hS obtain ⟨hS_clique, hS_card⟩ := hS
A subset s ⊆ V \ {x} is an (r-1)-clique in (G - x) + ab if and only if its image φ(s) is an (r-1)-clique in G + ab.
Two vertices u, v in V \ {x} are adjacent in (G - x) + ab if and only if they are adjacent in G + ab (`key`), because G - x is an induced subgraph and the added edge {a, b} is identical in both graphs. Consequently, s is a clique in (G - x) + ab if and only if φ(s) is a clique in G + ab (`clique_iff`). Since φ is an embedding, |s| = |φ(s)|, so s is an (r-1)-clique in (G - x) + ab if and only if φ(s) is an (r-1)-clique in G + ab (`nclique_iff`).
uses
SimpleGraph.sup_adj,SimpleGraph.induce_adj,SimpleGraph.fromEdgeSet_adj,SimpleGraph.isClique_iff,SimpleGraph.isNClique_iff,Finset.card_maphave key : ∀ u v : ↥(Set.univ \ ({x} : Set V)), ((G.induce (Set.univ \ ({x} : Set V))) ⊔ SimpleGraph.fromEdgeSet {s(a,b)}).Adj u v ↔ (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).Adj (u:V) (v:V) := by intro u v rw [SimpleGraph.sup_adj, SimpleGraph.sup_adj] constructor · rintro (h | h) · left; exact (SimpleGraph.induce_adj).mp h · right rw [SimpleGraph.fromEdgeSet_adj] at h ⊢ obtain ⟨hmem, hne⟩ := h refine ⟨?_, ?_⟩ · simp only [Set.mem_singleton_iff] at hmem ⊢ rw [← Sym2.map_mk (Subtype.val) u v, ← Sym2.map_mk (Subtype.val) a b] exact congrArg (Sym2.map (Subtype.val : ↥(Set.univ \ ({x} : Set V)) → V)) hmem · exact fun hh => hne (Subtype.val_injective hh) · rintro (h | h) · left; exact (SimpleGraph.induce_adj).mpr h · right rw [SimpleGraph.fromEdgeSet_adj] at h ⊢ obtain ⟨hmem, hne⟩ := h refine ⟨?_, ?_⟩ · rw [Set.mem_singleton_iff] at hmem rw [Set.mem_singleton_iff, Sym2.eq_iff] rw [Sym2.eq_iff] at hmem rcases hmem with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Or.inl ⟨Subtype.val_injective h1, Subtype.val_injective h2⟩ · exact Or.inr ⟨Subtype.val_injective h1, Subtype.val_injective h2⟩ · exact fun hh => hne (congrArg Subtype.val hh) have clique_iff : ∀ s : Finset ↥(Set.univ \ ({x} : Set V)), ((G.induce (Set.univ \ ({x} : Set V))) ⊔ SimpleGraph.fromEdgeSet {s(a,b)}).IsClique (↑s) ↔ (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsClique (↑(s.map φ)) := by intro s rw [SimpleGraph.isClique_iff, SimpleGraph.isClique_iff] constructor · intro h p hp q hq hpq rw [Finset.mem_coe, Finset.mem_map] at hp hq obtain ⟨u, hu, rfl⟩ := hp obtain ⟨v, hv, rfl⟩ := hq have huv : u ≠ v := fun hc => hpq (by rw [hc]) exact (key u v).mp (h (Finset.mem_coe.mpr hu) (Finset.mem_coe.mpr hv) huv) · intro h u hu v hv huv rw [Finset.mem_coe] at hu hv exact (key u v).mpr (h (Finset.mem_coe.mpr ((Finset.mem_map).mpr ⟨u, hu, rfl⟩)) (Finset.mem_coe.mpr ((Finset.mem_map).mpr ⟨v, hv, rfl⟩)) (fun hc => huv (φ.injective hc))) have nclique_iff : ∀ s : Finset ↥(Set.univ \ ({x} : Set V)), ((G.induce (Set.univ \ ({x} : Set V))) ⊔ SimpleGraph.fromEdgeSet {s(a,b)}).IsNClique (r-1) s ↔ (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsNClique (r-1) (s.map φ) := by intro s rw [SimpleGraph.isNClique_iff, SimpleGraph.isNClique_iff, clique_iff s, Finset.card_map]
The unique r-clique S in G + ab contains the universal vertex x.
Suppose, for contradiction, that x ∉ S. Since |S| = r ≥ 3, S is nonempty, so we can pick a vertex c ∈ S. Consider S' = (S \ {c}) ∪ {x}. As a subset of a clique, S \ {c} is a clique in G + ab. Because x is universal in G, it is adjacent in G (and thus in G + ab) to every vertex of S \ {c}, making S' a clique in G + ab. Its cardinality is |S| - 1 + 1 = r, so S' is an r-clique in G + ab. By the uniqueness of S (`hSuniq`), S' = S, which contradicts x ∉ S since x ∈ S'. Thus x ∈ S.
uses
Finset.card_pos,Finset.coe_insert,SimpleGraph.isClique_insert,SimpleGraph.IsClique.subset,Finset.coe_erase,SimpleGraph.sup_adj,Finset.card_insert_of_notMem,Finset.card_erase_of_mem,SimpleGraph.isNClique_iff,Finset.mem_insert_selfhave hxS : x ∈ S := by by_contra hxS have hSpos : 0 < S.card := by rw [hS_card]; omega obtain ⟨c, hcS⟩ := Finset.card_pos.mp hSpos have hc' : x ∉ S.erase c := by simp [hxS] have hS'_clique : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsClique (↑(insert x (S.erase c)) : Set V) := by rw [Finset.coe_insert, SimpleGraph.isClique_insert] refine ⟨?_, ?_⟩ · apply SimpleGraph.IsClique.subset _ hS_clique intro y hy rw [Finset.coe_erase] at hy exact hy.1 · intro y hy hxy rw [SimpleGraph.sup_adj] exact Or.inl (hx hxy) have hS'_card : (insert x (S.erase c)).card = r := by rw [Finset.card_insert_of_notMem hc', Finset.card_erase_of_mem hcS, hS_card] omega have hS' : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsNClique r (insert x (S.erase c)) := by rw [SimpleGraph.isNClique_iff]; exact ⟨hS'_clique, hS'_card⟩ have huniqS := hSuniq _ hS' have : x ∈ S := by rw [← huniqS]; exact Finset.mem_insert_self x _ exact hxS this
Deleting x from S yields an (r-1)-clique t = S \ {x} in (G - x) + ab.
Since x ∈ S and S is an r-clique in G + ab, the set S \ {x} has cardinality r - 1 and is a clique in G + ab. Since it avoids x, it pulls back via φ to a subset t of V \ {x} with φ(t) = S \ {x}. By the clique correspondence from Step 4, t is an (r-1)-clique in (G - x) + ab, establishing existence.
uses
Finset.filter_true_of_mem,Finset.mem_erase,Finset.subtype_map,SimpleGraph.isNClique_iff,SimpleGraph.IsClique.subset,Finset.coe_erase,Finset.card_erase_of_memlet p : V → Prop := fun v => v ∈ (Set.univ \ ({x} : Set V)) let t : Finset ↥(Set.univ \ ({x} : Set V)) := Finset.subtype p (S.erase x) have hfilt : Finset.filter p (S.erase x) = S.erase x := by apply Finset.filter_true_of_mem intro y hy rw [Finset.mem_erase] at hy obtain ⟨hyx, hyS⟩ := hy simp only [p, Set.mem_sdiff, Set.mem_univ, Set.mem_singleton_iff, true_and] exact hyx have ht_map : t.map φ = S.erase x := by have h := Finset.subtype_map p (s := S.erase x) rw [hfilt] at h exact h have ht : ((G.induce (Set.univ \ ({x} : Set V))) ⊔ SimpleGraph.fromEdgeSet {s(a,b)}).IsNClique (r-1) t := by rw [nclique_iff t, ht_map, SimpleGraph.isNClique_iff] refine ⟨?_, ?_⟩ · apply SimpleGraph.IsClique.subset _ hS_clique intro y hy rw [Finset.coe_erase] at hy exact hy.1 · rw [Finset.card_erase_of_mem hxS, hS_card] refine ⟨t, ht, ?_⟩
The clique t is the unique (r-1)-clique in (G - x) + ab.
Let t' be any (r-1)-clique in (G - x) + ab. By the clique correspondence, φ(t') is an (r-1)-clique in G + ab avoiding x. Adding the universal vertex x yields a clique φ(t') ∪ {x} in G + ab of cardinality (r - 1) + 1 = r. By the uniqueness of S as the only r-clique in G + ab (`hSuniq`), φ(t') ∪ {x} = S. Erasing x gives φ(t') = S \ {x} = φ(t). By the injectivity of φ on finite sets (`Finset.map_injective`), t' = t.
uses
Finset.mem_map,Finset.coe_insert,SimpleGraph.isClique_insert,SimpleGraph.sup_adj,Finset.card_insert_of_notMem,SimpleGraph.isNClique_iff,Finset.erase_insert,Finset.map_injectiveintro t' ht' have ht'_map : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsNClique (r-1) (t'.map φ) := (nclique_iff t').mp ht' have hx_notin : x ∉ t'.map φ := by rw [Finset.mem_map] rintro ⟨a', ha', hax⟩ exact (hanx a') hax have hT'_clique : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsClique (↑(insert x (t'.map φ)) : Set V) := by rw [Finset.coe_insert, SimpleGraph.isClique_insert] refine ⟨ht'_map.1, ?_⟩ intro y hy hxy rw [SimpleGraph.sup_adj] exact Or.inl (hx hxy) have hT'_card : (insert x (t'.map φ)).card = r := by rw [Finset.card_insert_of_notMem hx_notin] have h := ht'_map.2 omega have hT' : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsNClique r (insert x (t'.map φ)) := by rw [SimpleGraph.isNClique_iff]; exact ⟨hT'_clique, hT'_card⟩ have hEq : insert x (t'.map φ) = S := hSuniq _ hT' have ht'_map2 : t'.map φ = S.erase x := by rw [← hEq, Finset.erase_insert hx_notin] rw [← ht_map] at ht'_map2 exact Finset.map_injective φ ht'_map2
SimpleGraph.isNClique_iff- A finite set of vertices is an n-clique if and only if it is a clique and has cardinality n.
SimpleGraph.IsClique.map- The image of a clique under a graph embedding is a clique in the mapped graph.
SimpleGraph.map_adj- Two vertices are adjacent in a mapped graph under an embedding if and only if they are the images of adjacent vertices.
SimpleGraph.induce_adj- Two vertices in an induced subgraph are adjacent if and only if they are adjacent in the ambient graph.
SimpleGraph.IsClique.mono- If G is a subgraph of H, any clique in G is also a clique in H.
Finset.coe_map- Coercing the image of a finset under an embedding to a set equals the set-theoretic image.
Finset.mem_map- An element belongs to the image of a finset under an embedding if and only if it is the image of an element of the finset.
Finset.card_map- An embedding preserves the cardinality of a finite set.
Finset.coe_insert- Inserting an element into a finite set commutes with coercion to a set.
SimpleGraph.isClique_insert- Inserting a vertex into a set yields a clique if and only if the set is a clique and the vertex is adjacent to every vertex in the set.
Finset.card_insert_of_notMem- Inserting an element into a finite set not containing it increments its cardinality by 1.
Sym2.ind- Induction principle for unordered pairs: a property holds for all pairs if it holds for pairs of the form s(x, y).
SimpleGraph.mem_edgeSet- An unordered pair belongs to the edge set of a graph if and only if its endpoints are adjacent.
SimpleGraph.compl_adj- Two vertices are adjacent in the complement graph if and only if they are distinct and non-adjacent in the original graph.
SimpleGraph.sup_adj- Two vertices are adjacent in the union of two graphs if and only if they are adjacent in at least one of them.
SimpleGraph.fromEdgeSet_adj- Two vertices are adjacent in the graph generated by an edge set if and only if their pair is in the set and they are distinct.
SimpleGraph.isClique_iff- A set of vertices is a clique if and only if every pair of distinct vertices in it is adjacent.
Finset.card_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
SimpleGraph.IsClique.subset- A subset of a clique is also a clique.
Finset.coe_erase- Coercing a finset after erasing an element equals the coerced set minus the singleton.
Finset.card_erase_of_mem- Erasing an element from a finite set containing it decreases its cardinality by 1.
Finset.mem_insert_self- An element is a member of the set obtained by inserting that element.
Finset.filter_true_of_mem- Filtering a finite set by a predicate that holds for all its members leaves the set unchanged.
Finset.mem_erase- An element is in s.erase b if and only if it is in s and not equal to b.
Finset.subtype_map- Mapping a filtered subtype finset back to the ambient type via the subtype embedding recovers the filtered finset.
Finset.erase_insert- Erasing an element after inserting it returns the original set, provided the element was not already present.
Finset.map_injective- An embedding between types induces an injective map on finite sets.
Function.Embedding.subtype- The canonical embedding from a subtype into its ambient type.
is_uniquely_clique_saturated- A graph is uniquely K_r-saturated if it contains no r-clique, but adding any non-edge creates a unique r-clique.
- The proof uses the subtype embedding φ : V \ {x} ↪ V to transfer cliques between the induced subgraph G - x and the ambient graph G.
- The technical equivalence lemmas `key` (lines 58–86) and `nclique_iff` (lines 105–109) bridge the gap between adding an edge to the induced subgraph and adding the corresponding edge to the ambient graph.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Deleting a universal vertex from a uniquely K_r-saturated graph yields a uniquely K_{r-1}-saturated graph. -/theorem uniquely_clique_saturated_vertex_deleted_of_universal {V : Type*} [Fintype V] (G : SimpleGraph V) {r : ℕ} (hr : 3 ≤ r) (hG : is_uniquely_clique_saturated G r) (x : V) (hx : G.IsUniversal x) : is_uniquely_clique_saturated (G.induce (Set.univ \ {x})) (r - 1) := by classical rw [is_uniquely_clique_saturated] at hG ⊢ obtain ⟨hno, huniq⟩ := hG let φ : ↥(Set.univ \ ({x} : Set V)) ↪ V := Function.Embedding.subtype (fun v => v ∈ (Set.univ \ ({x} : Set V))) have hanx : ∀ (a : ↥(Set.univ \ ({x} : Set V))), (a:V) ≠ x := fun a => by simpa using a.property.2 constructor · intro s hs rw [SimpleGraph.isNClique_iff] at hs obtain ⟨hclique, hcard⟩ := hs have h1 : (SimpleGraph.map (⇑φ) (G.induce (Set.univ \ ({x} : Set V)))).IsClique (⇑φ '' ↑s) := SimpleGraph.IsClique.map hclique (f := φ) have hle : SimpleGraph.map (⇑φ) (G.induce (Set.univ \ ({x} : Set V))) ≤ G := by intro a b hab rw [SimpleGraph.map_adj] at hab obtain ⟨a', b', hadj, ha, hb⟩ := hab rw [← ha, ← hb] exact (SimpleGraph.induce_adj).mp hadj have h2 : G.IsClique (⇑φ '' ↑s) := SimpleGraph.IsClique.mono hle h1 rw [← Finset.coe_map] at h2 have hxnotmem : x ∉ s.map φ := by rw [Finset.mem_map] rintro ⟨a, ha, hax⟩ exact (hanx a) hax have hcard' : (s.map φ).card = r - 1 := by rw [Finset.card_map, hcard] have h3 : G.IsClique (↑(insert x (s.map φ)) : Set V) := by rw [Finset.coe_insert] rw [SimpleGraph.isClique_insert] refine ⟨h2, ?_⟩ intro b hb hxb exact hx hxb have h4 : (insert x (s.map φ)).card = r := by rw [Finset.card_insert_of_notMem hxnotmem, hcard'] omega exact hno _ (by rw [SimpleGraph.isNClique_iff]; exact ⟨h3, h4⟩) · intro e induction e using Sym2.ind with | _ a b => intro hab rw [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj] at hab obtain ⟨habne, habnotadj⟩ := hab have hGnotadj : ¬ G.Adj (a:V) (b:V) := by simpa only [SimpleGraph.induce_adj] using habnotadj have hne' : (a:V) ≠ (b:V) := fun h => habne (φ.injective h) have he' : s((a:V),(b:V)) ∈ Gᶜ.edgeSet := by rw [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj] exact ⟨hne', hGnotadj⟩ obtain ⟨S, hS, hSuniq⟩ := huniq _ he' rw [SimpleGraph.isNClique_iff] at hS obtain ⟨hS_clique, hS_card⟩ := hS have key : ∀ u v : ↥(Set.univ \ ({x} : Set V)), ((G.induce (Set.univ \ ({x} : Set V))) ⊔ SimpleGraph.fromEdgeSet {s(a,b)}).Adj u v ↔ (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).Adj (u:V) (v:V) := by intro u v rw [SimpleGraph.sup_adj, SimpleGraph.sup_adj] constructor · rintro (h | h) · left; exact (SimpleGraph.induce_adj).mp h · right rw [SimpleGraph.fromEdgeSet_adj] at h ⊢ obtain ⟨hmem, hne⟩ := h refine ⟨?_, ?_⟩ · simp only [Set.mem_singleton_iff] at hmem ⊢ rw [← Sym2.map_mk (Subtype.val) u v, ← Sym2.map_mk (Subtype.val) a b] exact congrArg (Sym2.map (Subtype.val : ↥(Set.univ \ ({x} : Set V)) → V)) hmem · exact fun hh => hne (Subtype.val_injective hh) · rintro (h | h) · left; exact (SimpleGraph.induce_adj).mpr h · right rw [SimpleGraph.fromEdgeSet_adj] at h ⊢ obtain ⟨hmem, hne⟩ := h refine ⟨?_, ?_⟩ · rw [Set.mem_singleton_iff] at hmem rw [Set.mem_singleton_iff, Sym2.eq_iff] rw [Sym2.eq_iff] at hmem rcases hmem with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Or.inl ⟨Subtype.val_injective h1, Subtype.val_injective h2⟩ · exact Or.inr ⟨Subtype.val_injective h1, Subtype.val_injective h2⟩ · exact fun hh => hne (congrArg Subtype.val hh) have clique_iff : ∀ s : Finset ↥(Set.univ \ ({x} : Set V)), ((G.induce (Set.univ \ ({x} : Set V))) ⊔ SimpleGraph.fromEdgeSet {s(a,b)}).IsClique (↑s) ↔ (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsClique (↑(s.map φ)) := by intro s rw [SimpleGraph.isClique_iff, SimpleGraph.isClique_iff] constructor · intro h p hp q hq hpq rw [Finset.mem_coe, Finset.mem_map] at hp hq obtain ⟨u, hu, rfl⟩ := hp obtain ⟨v, hv, rfl⟩ := hq have huv : u ≠ v := fun hc => hpq (by rw [hc]) exact (key u v).mp (h (Finset.mem_coe.mpr hu) (Finset.mem_coe.mpr hv) huv) · intro h u hu v hv huv rw [Finset.mem_coe] at hu hv exact (key u v).mpr (h (Finset.mem_coe.mpr ((Finset.mem_map).mpr ⟨u, hu, rfl⟩)) (Finset.mem_coe.mpr ((Finset.mem_map).mpr ⟨v, hv, rfl⟩)) (fun hc => huv (φ.injective hc))) have nclique_iff : ∀ s : Finset ↥(Set.univ \ ({x} : Set V)), ((G.induce (Set.univ \ ({x} : Set V))) ⊔ SimpleGraph.fromEdgeSet {s(a,b)}).IsNClique (r-1) s ↔ (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsNClique (r-1) (s.map φ) := by intro s rw [SimpleGraph.isNClique_iff, SimpleGraph.isNClique_iff, clique_iff s, Finset.card_map] have hxS : x ∈ S := by by_contra hxS have hSpos : 0 < S.card := by rw [hS_card]; omega obtain ⟨c, hcS⟩ := Finset.card_pos.mp hSpos have hc' : x ∉ S.erase c := by simp [hxS] have hS'_clique : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsClique (↑(insert x (S.erase c)) : Set V) := by rw [Finset.coe_insert, SimpleGraph.isClique_insert] refine ⟨?_, ?_⟩ · apply SimpleGraph.IsClique.subset _ hS_clique intro y hy rw [Finset.coe_erase] at hy exact hy.1 · intro y hy hxy rw [SimpleGraph.sup_adj] exact Or.inl (hx hxy) have hS'_card : (insert x (S.erase c)).card = r := by rw [Finset.card_insert_of_notMem hc', Finset.card_erase_of_mem hcS, hS_card] omega have hS' : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsNClique r (insert x (S.erase c)) := by rw [SimpleGraph.isNClique_iff]; exact ⟨hS'_clique, hS'_card⟩ have huniqS := hSuniq _ hS' have : x ∈ S := by rw [← huniqS]; exact Finset.mem_insert_self x _ exact hxS this let p : V → Prop := fun v => v ∈ (Set.univ \ ({x} : Set V)) let t : Finset ↥(Set.univ \ ({x} : Set V)) := Finset.subtype p (S.erase x) have hfilt : Finset.filter p (S.erase x) = S.erase x := by apply Finset.filter_true_of_mem intro y hy rw [Finset.mem_erase] at hy obtain ⟨hyx, hyS⟩ := hy simp only [p, Set.mem_sdiff, Set.mem_univ, Set.mem_singleton_iff, true_and] exact hyx have ht_map : t.map φ = S.erase x := by have h := Finset.subtype_map p (s := S.erase x) rw [hfilt] at h exact h have ht : ((G.induce (Set.univ \ ({x} : Set V))) ⊔ SimpleGraph.fromEdgeSet {s(a,b)}).IsNClique (r-1) t := by rw [nclique_iff t, ht_map, SimpleGraph.isNClique_iff] refine ⟨?_, ?_⟩ · apply SimpleGraph.IsClique.subset _ hS_clique intro y hy rw [Finset.coe_erase] at hy exact hy.1 · rw [Finset.card_erase_of_mem hxS, hS_card] refine ⟨t, ht, ?_⟩ intro t' ht' have ht'_map : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsNClique (r-1) (t'.map φ) := (nclique_iff t').mp ht' have hx_notin : x ∉ t'.map φ := by rw [Finset.mem_map] rintro ⟨a', ha', hax⟩ exact (hanx a') hax have hT'_clique : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsClique (↑(insert x (t'.map φ)) : Set V) := by rw [Finset.coe_insert, SimpleGraph.isClique_insert] refine ⟨ht'_map.1, ?_⟩ intro y hy hxy rw [SimpleGraph.sup_adj] exact Or.inl (hx hxy) have hT'_card : (insert x (t'.map φ)).card = r := by rw [Finset.card_insert_of_notMem hx_notin] have h := ht'_map.2 omega have hT' : (G ⊔ SimpleGraph.fromEdgeSet {s((a:V),(b:V))}).IsNClique r (insert x (t'.map φ)) := by rw [SimpleGraph.isNClique_iff]; exact ⟨hT'_clique, hT'_card⟩ have hEq : insert x (t'.map φ) = S := hSuniq _ hT' have ht'_map2 : t'.map φ = S.erase x := by rw [← hEq, Finset.erase_insert hx_notin] rw [← ht_map] at ht'_map2 exact Finset.map_injective φ ht'_map2