AFTD Auto-Formalizing Theoretical Domains

simple_graph_delete_vertex_preserves_smaller_edge_cliques

theoremverified

If every edge of a finite simple graph lies in a clique of size k+1, then after deleting any vertex every remaining edge lies in a clique of size k, provided k is at least two.

Statement

theorem simple_graph_delete_vertex_preserves_smaller_edge_cliques
    (α : Type) [Fintype α] [DecidableEq α] (G : SimpleGraph α) (k : ℕ) (hk : 2 ≤ k)
    (hclique : ∀ u v, G.Adj u v → ∃ S : Finset α,
      S.card = k + 1 ∧ u ∈ S ∧ v ∈ S ∧ G.IsClique (S : Set α))
    (x : α) :
    ∀ u v : {a : α // a ≠ x}, (G.induce {a | a ≠ x}).Adj u v →
      ∃ S : Finset {a : α // a ≠ x}, S.card = k ∧ u ∈ S ∧ v ∈ S ∧
        (G.induce {a | a ≠ x}).IsClique (S : Set {a : α // a ≠ x})
Source
Induced-subgraph step in the overlap-to-regularity route for OP-110.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To show that any remaining edge {u, v} in G - x lies in a k-clique, we take a (k+1)-clique S containing {u, v} in G and drop one vertex. If x ∈ S, we delete x; if x ∉ S, we delete a third vertex w ∈ S \ {u, v}, which exists because |S \ {u, v}| = k - 1 ≥ 1 by the assumption k ≥ 2. The resulting k-element clique avoids x and restricts to a k-clique containing {u, v} in the induced subgraph.

  1. The edge between u and v in the induced subgraph corresponds to an edge in G, which lies in a (k+1)-clique S of G.

    Given an edge between vertices u and v in the induced subgraph G - x, `SimpleGraph.induce_adj` shows that u and v are adjacent in the original graph G. By the theorem's clique hypothesis, there exists a clique S of size k+1 in G containing both u and v.

    lines 9–11

    uses SimpleGraph.induce_adj

      intro u v huv
      have hG : G.Adj u.1 v.1 := (SimpleGraph.induce_adj).mp huv
      obtain ⟨S, hScard, huS, hvS, hSclique⟩ := hclique u.1 v.1 hG
  2. If x ∈ S, removing x yields a k-clique T in G avoiding x and containing both u and v.

    We split into cases on whether x ∈ S. When x ∈ S, we choose T = S \ {x}. By `Finset.card_erase_of_mem`, its cardinality is (k + 1) - 1 = k. Because u and v are vertices of G - x, neither is x, so both remain in T by `Finset.mem_erase.mpr`. By definition of erasing, every element of T is distinct from x (`Finset.mem_erase.mp`), and T is a clique in G as a subset of the clique S.

    lines 12–20

    uses Finset.card_erase_of_mem, Finset.mem_erase.mpr, Finset.mem_erase.mp

      have key : ∃ T : Finset α, T.card = k ∧ u.1 ∈ T ∧ v.1 ∈ T ∧
          (∀ a ∈ T, a ≠ x) ∧ G.IsClique (T : Set α) := by
        by_cases hxS : x ∈ S
        · refine ⟨S.erase x, ?_, ?_, ?_, ?_, ?_⟩
          · rw [Finset.card_erase_of_mem hxS, hScard]; omega
          · exact Finset.mem_erase.mpr ⟨u.2, huS⟩
          · exact Finset.mem_erase.mpr ⟨v.2, hvS⟩
          · intro a ha; exact (Finset.mem_erase.mp ha).1
          · exact hSclique.subset (by intro a ha; exact (Finset.mem_erase.mp ha).2)
  3. If x ∉ S, removing an auxiliary vertex w ∈ S \ {u, v} yields a k-clique T in G avoiding x and containing both u and v.

    When x ∉ S, the clique S already avoids x, but has size k+1. Since u and v are adjacent, they are distinct vertices in S. Successively removing u and v from S leaves a set of size (k + 1) - 2 = k - 1 by `Finset.card_erase_of_mem`. Because k ≥ 2, this remainder has cardinality at least 1, so by `Finset.card_pos.mp` it contains some element w. By `Finset.mem_erase.mp`, w belongs to S and is distinct from both u and v. Defining T = S \ {w}, its cardinality is k by `Finset.card_erase_of_mem`, it retains u and v by `Finset.mem_erase.mpr`, it avoids x because S did, and it is a clique in G as a subset of S.

    lines 21–38

    uses Finset.mem_erase.mpr, Finset.card_erase_of_mem, Finset.card_pos.mp, Finset.mem_erase.mp

        · have hvA : v.1 ∈ S.erase u.1 := Finset.mem_erase.mpr ⟨hG.ne.symm, hvS⟩
          have hA : (S.erase u.1).card = k := by
            rw [Finset.card_erase_of_mem huS, hScard]; omega
          have hEv : ((S.erase u.1).erase v.1).card = k - 1 := by
            rw [Finset.card_erase_of_mem hvA, hA]
          have hpos : 0 < ((S.erase u.1).erase v.1).card := by omega
          obtain ⟨w, hw⟩ := Finset.card_pos.mp hpos
          have hw_ne_v : w ≠ v.1 := (Finset.mem_erase.mp hw).1
          have hw_in_A : w ∈ S.erase u.1 := (Finset.mem_erase.mp hw).2
          have hw_ne_u : w ≠ u.1 := (Finset.mem_erase.mp hw_in_A).1
          have hwS : w ∈ S := (Finset.mem_erase.mp hw_in_A).2
          refine ⟨S.erase w, ?_, ?_, ?_, ?_, ?_⟩
          · rw [Finset.card_erase_of_mem hwS, hScard]; omega
          · exact Finset.mem_erase.mpr ⟨hw_ne_u.symm, huS⟩
          · exact Finset.mem_erase.mpr ⟨hw_ne_v.symm, hvS⟩
          · intro a ha h
            exact hxS (h ▸ (Finset.mem_erase.mp ha).2)
          · exact hSclique.subset (by intro a ha; exact (Finset.mem_erase.mp ha).2)
  4. The set T determines a k-clique containing u and v in the induced subgraph G - x.

    Having obtained a k-clique T in G containing u and v and avoiding x, we convert T to a finset of the subtype {a // a ≠ x}. Since all elements of T satisfy the predicate, the subtype set has cardinality k by `Finset.card_subtype` and `Finset.filter_true_of_mem`. The vertices u and v belong to this set by `Finset.mem_subtype.mpr`. Finally, two distinct elements in this subtype set have distinct underlying vertices by `Subtype.ext`, so they are adjacent in G by `Finset.mem_subtype.mp`, which by `SimpleGraph.induce_adj` means they are adjacent in the induced subgraph.

    lines 39–47

    uses Finset.card_subtype, Finset.filter_true_of_mem, Finset.mem_subtype.mpr, SimpleGraph.induce_adj, Finset.mem_subtype.mp, Subtype.ext

      obtain ⟨T, hTcard, huT, hvT, hTsub, hTclique⟩ := key
      refine ⟨Finset.subtype (fun a : α => a ≠ x) T, ?_, ?_, ?_, ?_⟩
      · rw [Finset.card_subtype, Finset.filter_true_of_mem hTsub, hTcard]
      · exact Finset.mem_subtype.mpr huT
      · exact Finset.mem_subtype.mpr hvT
      · intro a ha b hb hab
        rw [SimpleGraph.induce_adj]
        exact hTclique (Finset.mem_subtype.mp ha) (Finset.mem_subtype.mp hb)
          (fun h => hab (Subtype.ext h))
Finset.card_erase_of_mem
Removing an element from a finite set decreases its cardinality by one.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.card_subtype
The cardinality of a subtype finset equals the cardinality of the ambient finset filtered by the predicate.
Finset.filter_true_of_mem
Filtering a finite set by a predicate that holds for all of its elements leaves the set unchanged.
Finset.mem_erase.mp
An element belonging to `s.erase a` belongs to `s` and is not equal to `a`.
Finset.mem_erase.mpr
An element that belongs to `s` and is not equal to `a` belongs to `s.erase a`.
Finset.mem_subtype.mp
If a subtype element belongs to a subtype finset, its underlying value belongs to the ambient finset.
Finset.mem_subtype.mpr
A subtype element whose underlying value belongs to the ambient finset belongs to the corresponding subtype finset.
SimpleGraph.induce_adj
Two vertices in an induced subgraph are adjacent if and only if they are adjacent in the ambient graph.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.

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

theorem simple_graph_delete_vertex_preserves_smaller_edge_cliques    (α : Type) [Fintype α] [DecidableEq α] (G : SimpleGraph α) (k : ℕ) (hk : 2 ≤ k)    (hclique : ∀ u v, G.Adj u v → ∃ S : Finset α,      S.card = k + 1 ∧ u ∈ S ∧ v ∈ S ∧ G.IsClique (S : Set α))    (x : α) :    ∀ u v : {a : α // a ≠ x}, (G.induce {a | a ≠ x}).Adj u v →      ∃ S : Finset {a : α // a ≠ x}, S.card = k ∧ u ∈ S ∧ v ∈ S ∧        (G.induce {a | a ≠ x}).IsClique (S : Set {a : α // a ≠ x}) := by  intro u v huv  have hG : G.Adj u.1 v.1 := (SimpleGraph.induce_adj).mp huv  obtain ⟨S, hScard, huS, hvS, hSclique⟩ := hclique u.1 v.1 hG  have key : ∃ T : Finset α, T.card = k ∧ u.1 ∈ T ∧ v.1 ∈ T ∧      (∀ a ∈ T, a ≠ x) ∧ G.IsClique (T : Set α) := by    by_cases hxS : x ∈ S    · refine ⟨S.erase x, ?_, ?_, ?_, ?_, ?_⟩      · rw [Finset.card_erase_of_mem hxS, hScard]; omega      · exact Finset.mem_erase.mpr ⟨u.2, huS⟩      · exact Finset.mem_erase.mpr ⟨v.2, hvS⟩      · intro a ha; exact (Finset.mem_erase.mp ha).1      · exact hSclique.subset (by intro a ha; exact (Finset.mem_erase.mp ha).2)    · have hvA : v.1 ∈ S.erase u.1 := Finset.mem_erase.mpr ⟨hG.ne.symm, hvS⟩      have hA : (S.erase u.1).card = k := by        rw [Finset.card_erase_of_mem huS, hScard]; omega      have hEv : ((S.erase u.1).erase v.1).card = k - 1 := by        rw [Finset.card_erase_of_mem hvA, hA]      have hpos : 0 < ((S.erase u.1).erase v.1).card := by omega      obtain ⟨w, hw⟩ := Finset.card_pos.mp hpos      have hw_ne_v : w ≠ v.1 := (Finset.mem_erase.mp hw).1      have hw_in_A : w ∈ S.erase u.1 := (Finset.mem_erase.mp hw).2      have hw_ne_u : w ≠ u.1 := (Finset.mem_erase.mp hw_in_A).1      have hwS : w ∈ S := (Finset.mem_erase.mp hw_in_A).2      refine ⟨S.erase w, ?_, ?_, ?_, ?_, ?_⟩      · rw [Finset.card_erase_of_mem hwS, hScard]; omega      · exact Finset.mem_erase.mpr ⟨hw_ne_u.symm, huS⟩      · exact Finset.mem_erase.mpr ⟨hw_ne_v.symm, hvS⟩      · intro a ha h        exact hxS (h ▸ (Finset.mem_erase.mp ha).2)      · exact hSclique.subset (by intro a ha; exact (Finset.mem_erase.mp ha).2)  obtain ⟨T, hTcard, huT, hvT, hTsub, hTclique⟩ := key  refine ⟨Finset.subtype (fun a : α => a ≠ x) T, ?_, ?_, ?_, ?_⟩  · rw [Finset.card_subtype, Finset.filter_true_of_mem hTsub, hTcard]  · exact Finset.mem_subtype.mpr huT  · exact Finset.mem_subtype.mpr hvT  · intro a ha b hb hab    rw [SimpleGraph.induce_adj]    exact hTclique (Finset.mem_subtype.mp ha) (Finset.mem_subtype.mp hb)      (fun h => hab (Subtype.ext h))
See it in the graphDiscuss this resultChallenge it