AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_edge_family_induce_map

theoremverified

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

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.

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

    lines 4–16

    uses Finset.ext, Finset.mem_filter.mp, Finset.sym2_map, Finset.mem_map.mp, Finset.mem_map.mpr, Finset.mem_filter.mpr

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

    lines 17–26

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

    lines 36–47

    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_injective

      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]
  4. 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$.

    lines 48–51

    uses Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and

      ext E
      simp only [simple_graph_triangle_edge_family, Finset.mem_image, Finset.mem_filter,
        Finset.mem_univ, true_and]
      constructor
  5. 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'$.

    lines 52–57

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

    lines 58–65

    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.

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

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