AFTD Auto-Formalizing Theoretical Domains

card_filter_singleton_prod

theoremverified

The number of directed edges in {v} × S is the number of neighbors of v in S.

Statement

theorem card_filter_singleton_prod {V : Type*}
    (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (S : Finset V) :
    (({v} ×ˢ S).filter (fun ⟨u, w⟩ => G.Adj u w)).card = (S.filter (fun w => G.Adj v w)).card
Source
step towards greedy_max_cut_half_edges_lower_bound
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 3
  • card_filter_prod_singletonThe number of directed edges in S × {v} is the number of neighbors of v in S.
  • greedy_cut_finset_boundFor every finite set of vertices A in a simple graph G, there is a subset S ⊆ A such that the number of cut edges between S and A \ S is…
  • greedy_max_cut_half_edges_lower_boundEvery finite simple graph G has a subset of vertices S such that the number of cut edges between S and V \ S is at least half the total…

The proof, explained

The Cartesian product $\{v\} \times S$ is identified with $S$ via the canonical embedding $w \mapsto (v, w)$. Commuting the edge filter with this embedding pulls the adjacency condition back to the property that $w$ is a neighbor of $v$ in $S$. Because embeddings preserve cardinality, the number of directed edges in $\{v\} \times S$ equals the number of neighbors of $v$ in $S$.

  1. Transporting along the canonical embedding $w \mapsto (v, w)$ identifies the edges in $\{v\} \times S$ with the neighbors of $v$ in $S$, establishing that $|(\{v\} \times S)\text{.filter}(G.\mathrm{Adj})| = |S\text{.filter}(G.\mathrm{Adj}\ v)|$.

    We rewrite the singleton product $\{v\} \times S$ as the image of $S$ under the embedding $w \mapsto (v, w)$ using `Finset.singleton_product`. Filtering this image by the edge relation commutes with the embedding by precomposing the predicate via `Finset.filter_map`, and `Finset.card_map` simplifies the cardinality of the mapped set to the cardinality of the filtered subset of $S$. Finally, the composite condition definitionally unpacks to $w \mapsto G.\mathrm{Adj}\ v\ w$, closing the equality by reflexivity (`rfl`).

    lines 5–6

    uses Finset.singleton_product, Finset.filter_map, Finset.card_map

      rw [Finset.singleton_product, Finset.filter_map, Finset.card_map]
      rfl
Finset.singleton_product
The Cartesian product $\{a\} \times t$ of a singleton with a finite set equals the image of $t$ under the embedding $w \mapsto (a, w)$.
Finset.filter_map
Filtering the image of a finite set under an embedding $f$ by a predicate $p$ is the image under $f$ of the set filtered by the precomposed predicate $p \circ f$.
Finset.card_map
An embedding preserves the cardinality of any finite set.

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

/-- The number of directed edges in {v} × S is the number of neighbors of v in S. -/theorem card_filter_singleton_prod {V : Type*}    (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (S : Finset V) :    (({v} ×ˢ S).filter (fun ⟨u, w⟩ => G.Adj u w)).card = (S.filter (fun w => G.Adj v w)).card := by  rw [Finset.singleton_product, Finset.filter_map, Finset.card_map]  rfl
See it in the graphDiscuss this resultChallenge it