simple_graph_triangle_edge_family_induce_map
The image of the triangle edge-family of an induced graph is exactly the original graph triangle edge-family restricted to triangles inside the retained vertex set.
Statement
open Classical theorem simple_graph_triangle_edge_family_induce_map {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (S : Finset V) : (simple_graph_triangle_edge_family (G.induce (S : Set V))).image (fun E => E.map (Function.Embedding.subtype (fun x => x ∈ S)).sym2Map) = (((Finset.univ : Finset (Finset V)).filter (fun t => G.IsNClique 3 t ∧ t ⊆ S)).image finite_vertex_set_edge_encoding)
- Source
- Induced-side transport for the published separator reduction, https://www.cs.tau.ac.il/~krivelev/2.pdf, Lemma 5.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
The proof, explained
To show that the triangle edge-family of an induced subgraph $G[S]$ pushes forward under the subtype embedding to the triangle edge-family of $G$ restricted to $S$, the proof proceeds by set extensionality. It first establishes that the edge-encoding operation commutes with the subtype embedding because the embedding is injective. The claim then follows from the fact that a vertex set in the induced graph is a 3-clique if and only if its embedded image is a 3-clique in the ambient graph.
For any embedding $f : \alpha \hookrightarrow \beta$ and finite set $s$, any edge in the encoding of $f(s)$ is the image under $f^{\{2\}}$ of an edge in the encoding of $s$.
We show the forward inclusion of `in519_vertex_edges_map`. By definition, an edge $e$ in the edge encoding of $f(s)$ is a non-diagonal pair in $(f(s))^{\{2\}}$. Since $(f(s))^{\{2\}} = f^{\{2\}}(s^{\{2\}})$ by `Finset.sym2_map`, $e = f^{\{2\}}(z)$ for some $z \in s^{\{2\}}$. If $z$ were diagonal, its image $e$ would also be diagonal, contradicting $e$ being non-diagonal. Hence $z$ is non-diagonal and belongs to the edge encoding of $s$.
uses
Finset.ext,Finset.mem_filter.mp,Finset.sym2_map,Finset.mem_map.mp,Finset.mem_map.mpr,Finset.mem_filter.mprclassical apply Finset.ext intro e constructor · intro he have he' := Finset.mem_filter.mp he rw [Finset.sym2_map] at he' obtain ⟨z,hz,rfl⟩ := Finset.mem_map.mp he'.1 apply Finset.mem_map.mpr refine ⟨z,Finset.mem_filter.mpr ⟨hz,?_⟩,rfl⟩ intro hzdiag apply he'.2 exact hzdiag.map
The edge encoding of an embedded vertex set $f(s)$ contains the image under $f^{\{2\}}$ of the edge encoding of $s$.
We show the reverse inclusion of `in519_vertex_edges_map`. An element in the image has the form $f^{\{2\}}(z)$ for a non-diagonal pair $z \in s^{\{2\}}$. Its image belongs to $(f(s))^{\{2\}}$ via `Finset.sym2_map`, and since $f$ is injective, `Sym2.isDiag_map` ensures that $f^{\{2\}}(z)$ cannot be diagonal because $z$ is not diagonal.
uses
Finset.mem_map.mp,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.sym2_map,Finset.mem_map.mpr,Sym2.isDiag_map· intro he obtain ⟨z,hz,rfl⟩ := Finset.mem_map.mp he have hz' := Finset.mem_filter.mp hz apply Finset.mem_filter.mpr refine ⟨?_,?_⟩ · rw [Finset.sym2_map] exact Finset.mem_map.mpr ⟨z,hz'.1,rfl⟩ · intro hzdiag apply hz'.2 exact (Sym2.isDiag_map f.injective).mp hzdiag
For any vertex subset $t'$ of the induced vertex set $S$, edge encoding commutes with the subtype embedding into $V$.
We establish the local lemma `henc` for the subtype inclusion $\iota : S \hookrightarrow V$. Unfolding the definition of edge encoding and commuting the pair construction with the embedding via `Finset.sym2_map` and `Finset.filter_map`, it suffices to show that a pair in $S^{\{2\}}$ is diagonal if and only if its image in $V^{\{2\}}$ is diagonal. This holds by `Sym2.isDiag_map` because the subtype projection `Subtype.val` is injective.
uses
Finset.sym2_map,Finset.filter_map,Finset.mem_filter,Function.comp,Function.Embedding.sym2Map_apply,Function.Embedding.coe_subtype,Sym2.isDiag_map,Subtype.val_injectivehave henc : ∀ t' : Finset (S : Set V), finite_vertex_set_edge_encoding (t'.map (Function.Embedding.subtype _)) = (finite_vertex_set_edge_encoding t').map (Function.Embedding.subtype (fun x => x ∈ S)).sym2Map := by intro t' simp only [finite_vertex_set_edge_encoding] rw [Finset.sym2_map, Finset.filter_map] congr 1 ext e simp only [Finset.mem_filter, Function.comp, Function.Embedding.sym2Map_apply, Function.Embedding.coe_subtype] rw [Sym2.isDiag_map Subtype.val_injective]
Extensionality reduces the equality of edge families to showing that an edge set $E$ is the mapped edge set of a 3-clique in $G[S]$ if and only if it is the edge set of a 3-clique in $G$ supported on $S$.
Applying extensionality (`ext E`) and unfolding the definitions of the triangle edge family and set operations with `simp only`, an edge set $E$ belongs to the LHS if it is the pushforward of the edge encoding of some 3-clique in $G[S]$, and belongs to the RHS if it is the edge encoding of a 3-clique in $G$ that is a subset of $S$.
uses
Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_andext E simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] constructor
Every edge set in the pushforward of the triangle edge family of $G[S]$ is the edge encoding of a 3-clique in $G$ contained in $S$.
Given a 3-clique $t'$ of $G[S]$, we map $t'$ into $V$ via the subtype embedding to obtain a triangle $t$ in $G$. By `SimpleGraph.isNClique_induce_iff`, $t$ is a 3-clique in $G$, and by definition of the subtype embedding, all its vertices lie in $S$. Applying `henc`, the edge encoding of $t$ equals the pushforward of the edge encoding of $t'$.
uses
SimpleGraph.isNClique_induce_iff,Finset.mem_map.mp· rintro ⟨E', ⟨t', ht', rfl⟩, rfl⟩ refine ⟨t'.map (Function.Embedding.subtype _), ⟨?_, ?_⟩, henc t'⟩ · exact (SimpleGraph.isNClique_induce_iff (G := G) (S : Set V) t' 3).mp ht' · intro x hx obtain ⟨y, _, rfl⟩ := Finset.mem_map.mp hx exact y.2
Every 3-clique of $G$ contained in $S$ arises from a unique 3-clique of the induced graph $G[S]$ with the same edge set.
Given a 3-clique $t$ of $G$ with $t \subseteq S$, we form its restriction $t'$ to the subtype $S$. Since $t \subseteq S$, mapping $t'$ back via the subtype embedding recovers $t$ by `Finset.subtype_map_of_mem`. By `SimpleGraph.isNClique_induce_iff`, $t'$ is a 3-clique in $G[S]$, and by `henc`, mapping the edge encoding of $t'$ recovers the edge encoding of $t$.
uses
Finset.subtype_map_of_mem,Finset.mem_coe.mpr,SimpleGraph.isNClique_induce_iff· rintro ⟨t, ⟨ht, hS⟩, rfl⟩ let t' : Finset (S : Set V) := t.subtype (fun x => x ∈ (S : Set V)) have hmap : t'.map (Function.Embedding.subtype _) = t := Finset.subtype_map_of_mem (fun x hx => Finset.mem_coe.mpr (hS hx)) refine ⟨finite_vertex_set_edge_encoding t', ⟨t', ?_, rfl⟩, ?_⟩ · rw [SimpleGraph.isNClique_induce_iff, hmap] exact ht · rw [← henc, hmap]
Finset.ext- Two finite sets are equal if and only if they contain the exact same elements.
Finset.mem_filter.mp- If an element belongs to a filtered finite set, it belongs to the underlying set and satisfies the filtering predicate.
Finset.mem_filter- Membership in a filtered finite set is equivalent to membership in the underlying set and satisfying the filtering predicate.
Finset.mem_filter.mpr- An element belongs to a filtered finite set if it belongs to the underlying set and satisfies the filtering predicate.
Finset.sym2_map- The unordered pairs of an embedded finite set equal the image of its unordered pairs under the induced embedding on pairs.
Finset.filter_map- Filtering the image of a finite set under an embedding by a predicate equals mapping the subset filtered by the pulled-back predicate.
Finset.mem_map.mp- If an element belongs to the image of a finite set under an embedding, it is the image of some element in that set.
Finset.mem_map.mpr- An element belongs to the image of a finite set under an embedding if it is the image of some element in that set.
Finset.mem_image- An element belongs to the image of a finite set under a function if and only if it is the image of some element in that set.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set `univ`.
Sym2.isDiag_map- For an injective map, an unordered pair is diagonal (a self-loop) if and only if its image under the map is diagonal.
Subtype.val_injective- The subtype projection `Subtype.val` is injective.
Function.Embedding.coe_subtype- The coercion of the subtype embedding to a function is the subtype projection `Subtype.val`.
Function.Embedding.sym2Map_apply- Applying the embedding on unordered pairs `sym2Map` induced by `f` agrees with `Sym2.map f`.
Function.comp- Function composition: `(g ∘ f)(x) = g(f(x))`.
true_and- Conjunction with `True` simplifies to the proposition itself: `True ∧ p ↔ p`.
SimpleGraph.isNClique_induce_iff- A finite vertex set in an induced subgraph `G.induce s` is an $n$-clique if and only if its image under the subtype embedding is an $n$-clique in `G`.
Finset.subtype_map_of_mem- If every element of a finite set `s` satisfies predicate `p`, mapping its restriction to the subtype `{x // p x}` back into the ambient type recovers `s`.
Finset.mem_coe.mpr- Membership of an element in a finite set implies membership in the set coerced to a set of the ambient type.
- The source begins with a private helper lemma `in519_vertex_edges_map` proving that edge encoding commutes with arbitrary embeddings, but the main proof reproves this fact directly (`henc`) for the subtype embedding of $S$ into $V$.
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.
private theorem in519_vertex_edges_map {α β : Type*} [DecidableEq α] [DecidableEq β] (f : α ↪ β) (s : Finset α) : finite_vertex_set_edge_encoding (s.map f) = (finite_vertex_set_edge_encoding s).map f.sym2Map := by classical apply Finset.ext intro e constructor · intro he have he' := Finset.mem_filter.mp he rw [Finset.sym2_map] at he' obtain ⟨z,hz,rfl⟩ := Finset.mem_map.mp he'.1 apply Finset.mem_map.mpr refine ⟨z,Finset.mem_filter.mpr ⟨hz,?_⟩,rfl⟩ intro hzdiag apply he'.2 exact hzdiag.map · intro he obtain ⟨z,hz,rfl⟩ := Finset.mem_map.mp he have hz' := Finset.mem_filter.mp hz apply Finset.mem_filter.mpr refine ⟨?_,?_⟩ · rw [Finset.sym2_map] exact Finset.mem_map.mpr ⟨z,hz'.1,rfl⟩ · intro hzdiag apply hz'.2 exact (Sym2.isDiag_map f.injective).mp hzdiagopen Classicaltheorem simple_graph_triangle_edge_family_induce_map {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (S : Finset V) : (simple_graph_triangle_edge_family (G.induce (S : Set V))).image (fun E => E.map (Function.Embedding.subtype (fun x => x ∈ S)).sym2Map) = (((Finset.univ : Finset (Finset V)).filter (fun t => G.IsNClique 3 t ∧ t ⊆ S)).image finite_vertex_set_edge_encoding) := by have henc : ∀ t' : Finset (S : Set V), finite_vertex_set_edge_encoding (t'.map (Function.Embedding.subtype _)) = (finite_vertex_set_edge_encoding t').map (Function.Embedding.subtype (fun x => x ∈ S)).sym2Map := by intro t' simp only [finite_vertex_set_edge_encoding] rw [Finset.sym2_map, Finset.filter_map] congr 1 ext e simp only [Finset.mem_filter, Function.comp, Function.Embedding.sym2Map_apply, Function.Embedding.coe_subtype] rw [Sym2.isDiag_map Subtype.val_injective] ext E simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨E', ⟨t', ht', rfl⟩, rfl⟩ refine ⟨t'.map (Function.Embedding.subtype _), ⟨?_, ?_⟩, henc t'⟩ · exact (SimpleGraph.isNClique_induce_iff (G := G) (S : Set V) t' 3).mp ht' · intro x hx obtain ⟨y, _, rfl⟩ := Finset.mem_map.mp hx exact y.2 · rintro ⟨t, ⟨ht, hS⟩, rfl⟩ let t' : Finset (S : Set V) := t.subtype (fun x => x ∈ (S : Set V)) have hmap : t'.map (Function.Embedding.subtype _) = t := Finset.subtype_map_of_mem (fun x hx => Finset.mem_coe.mpr (hS hx)) refine ⟨finite_vertex_set_edge_encoding t', ⟨t', ?_, rfl⟩, ?_⟩ · rw [SimpleGraph.isNClique_induce_iff, hmap] exact ht · rw [← henc, hmap]