AFTD Auto-Formalizing Theoretical Domains

card_filter_prod_singleton

theoremverified

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

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

    line 5

    uses Finset.product_singleton, Finset.filter_map, Finset.card_map

      rw [Finset.product_singleton, Finset.filter_map, Finset.card_map]
  2. 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.

    lines 6–8

    uses G.adj_comm

      congr 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

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