AFTD Auto-Formalizing Theoretical Domains

uniquely_clique_saturated_vertex_deleted_of_universal

theoremverified

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

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.

  1. 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.

    lines 7–14

    uses is_uniquely_clique_saturated, Function.Embedding.subtype

      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
  2. 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.

    lines 15–42

    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⟩)
  3. 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.

    lines 43–57

    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
  4. 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`).

    lines 58–109

    uses SimpleGraph.sup_adj, SimpleGraph.induce_adj, SimpleGraph.fromEdgeSet_adj, SimpleGraph.isClique_iff, SimpleGraph.isNClique_iff, Finset.card_map

          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]
  5. 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.

    lines 110–132

    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_self

          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
  6. 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.

    lines 133–154

    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_mem

          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, ?_⟩
  7. 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.

    lines 155–178

    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_injective

          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
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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it