card_filter_singleton_prod
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$.
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`).
uses
Finset.singleton_product,Finset.filter_map,Finset.card_maprw [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.
- Closing the goal with `rfl` on line 6 is a formal detail with no counterpart on paper: it performs the definitional reduction that simplifies the pattern-matching composition $((u, w) \mapsto G.\mathrm{Adj}\ u\ w) \circ (w \mapsto (v, w))$ to $w \mapsto G.\mathrm{Adj}\ v\ w$.
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.
/-- 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