simple_graph_delete_vertex_preserves_smaller_edge_cliques
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.
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.
uses
SimpleGraph.induce_adjintro 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
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.
uses
Finset.card_erase_of_mem,Finset.mem_erase.mpr,Finset.mem_erase.mphave 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)
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.
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)
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.
uses
Finset.card_subtype,Finset.filter_true_of_mem,Finset.mem_subtype.mpr,SimpleGraph.induce_adj,Finset.mem_subtype.mp,Subtype.extobtain ⟨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.
- Lean formalizes vertex deletion as the induced subgraph on the subtype `{a : α // a ≠ x}`. As a result, the proof explicitly constructs and converts between subsets of the ambient type `α` and subsets of the subtype using `Finset.subtype`, a technical step that is treated as an identification on paper.
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.
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))