card_filter_prod_singleton
The number of directed edges in S × {v} is the number of neighbors of v in S.
Statement
theorem card_filter_prod_singleton {V : Type*} (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (S : Finset V) : ((S ×ˢ {v}).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- Built on 1
- card_filter_singleton_prodThe number of directed edges in {v} × S is the number of neighbors of v in S.
- Used by 2
- 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 S × {v} embeds injectively into V × V via u ↦ (u, v), so edges in S × {v} correspond bijectively to vertices u ∈ S adjacent to v. By symmetry of adjacency in a simple graph, a vertex u is adjacent to v if and only if v is adjacent to u. Thus the two filtered sets coincide and have identical cardinality.
The number of edges in S × {v} equals the number of vertices u ∈ S adjacent to v.
The product S × {v} is rewritten as the image of S under the embedding u ↦ (u, v) using `Finset.product_singleton`. Commuting the filter with this embedding via `Finset.filter_map` pulls the edge condition back to S, producing the embedding applied to {u ∈ S | G.Adj u v}. Because embeddings preserve cardinality (`Finset.card_map`), this reduces the left-hand side to the size of {u ∈ S | G.Adj u v}.
uses
Finset.product_singleton,Finset.filter_map,Finset.card_maprw [Finset.product_singleton, Finset.filter_map, Finset.card_map]The set of vertices in S adjacent to v equals the set of vertices in S to which v is adjacent.
Equating cardinalities reduces to showing that the two filtered subsets of S are equal (`congr 1`). By set extensionality (`ext u`), an element u belongs to the first set if and only if u ∈ S and G.Adj u v, and to the second if and only if u ∈ S and G.Adj v u. Because adjacency in a simple graph is symmetric (`G.adj_comm`), these membership conditions are equivalent.
uses
G.adj_commcongr 1 ext u simp [G.adj_comm]
Finset.product_singleton- The Cartesian product of a finite set s with a singleton {b} is the image of s under the embedding i ↦ (i, b).
Finset.filter_map- Filtering the image of a set under an embedding f by a predicate p equals the image under f of the set filtered by p ∘ f.
Finset.card_map- Mapping a finite set along an injective function preserves its cardinality.
G.adj_comm- In a simple graph, adjacency is symmetric: u is adjacent to v if and only if v is adjacent to u.
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 S × {v} is the number of neighbors of v in S. -/theorem card_filter_prod_singleton {V : Type*} (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (S : Finset V) : ((S ×ˢ {v}).filter (fun ⟨u, w⟩ => G.Adj u w)).card = (S.filter (fun w => G.Adj v w)).card := by rw [Finset.product_singleton, Finset.filter_map, Finset.card_map] congr 1 ext u simp [G.adj_comm]