crossing_pairs_card_eq_crossing_edges_card
For a finite simple graph G and a vertex set A, the number of ordered adjacent pairs (a, b) with a ∈ A and b ∈ Aᶜ equals the number of edges of G crossing the cut (A, Aᶜ).
Statement
theorem crossing_pairs_card_eq_crossing_edges_card {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) : ((A ×ˢ Aᶜ).filter (fun p : V × V => G.Adj p.1 p.2)).card = (G.edgeFinset.filter (fun e => ∃ u ∈ A, ∃ v ∈ (Aᶜ : Finset V), e = s(u, v))).card
- Source
- step towards edge_connectivity_ge_min_degree_mul_lly_lower_bound_two
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- edge_connectivity_ge_min_degree_mul_lly_lower_bound_twoEvery finite connected graph of diameter 2 has κ'(G) ≥ δ(G) · κ_LLY^(2)(G).
- cross_cut_card_ge_minDegree_of_diam_twoPlesník's cut lemma: in a finite connected graph G with diam(G) = 2, every nontrivial vertex cut (A, Aᶜ) has at least δ(G) crossing edges.
The proof, explained
The proof establishes the equality of cardinalities by constructing a bijection between the set of adjacent ordered pairs (u, v) ∈ A × Aᶜ and the set of cut edges crossing (A, Aᶜ). The map sends each ordered pair (u, v) to the undirected edge s(u, v). Injectivity holds because an edge cannot be oriented in the reverse direction across the cut without violating the disjointness of A and Aᶜ, and surjectivity holds by the definition of a crossing edge.
To show the two sets have equal cardinality, it suffices to construct a bijection from adjacent ordered pairs (u, v) ∈ A × Aᶜ to cut edges s(u, v).
We apply `Finset.card_bij` using the map sending each ordered pair p to the undirected pair s(p.1, p.2). This reduces the theorem to three obligations: showing the map sends elements to the target set, is injective, and is surjective.
uses
Finset.card_bijrefine Finset.card_bij (fun p _ => s(p.1, p.2)) ?_ ?_ ?_
The map is well-defined: for any adjacent pair p ∈ A × Aᶜ, the unordered pair s(p.1, p.2) is a crossing edge of G.
Let p = (p.1, p.2) be in the domain. By definition of the Cartesian product and filtering condition, p.1 ∈ A, p.2 ∈ Aᶜ, and p.1 is adjacent to p.2 in G. By the adjacency condition, s(p.1, p.2) is in the edge set of G, and setting u = p.1 and v = p.2 witnesses that it is an edge crossing between A and Aᶜ.
uses
Finset.mem_filter,Finset.mem_product,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet· intro p hp rw [Finset.mem_filter] at hp ⊢ rcases hp with ⟨hp_prod, hp_adj⟩ rw [Finset.mem_product] at hp_prod refine ⟨?_, p.1, hp_prod.1, p.2, hp_prod.2, rfl⟩ rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] exact hp_adj
The map is injective: if two adjacent pairs in A × Aᶜ yield the same edge, the pairs must be identical.
Let p₁ and p₂ be pairs in A × Aᶜ such that s(p₁.1, p₁.2) = s(p₂.1, p₂.2). By equality of unordered pairs, either (p₁.1 = p₂.1 ∧ p₁.2 = p₂.2) or (p₁.1 = p₂.2 ∧ p₁.2 = p₂.1). In the first case, p₁ = p₂ directly. In the second case, p₁.1 = p₂.2 leads to a contradiction, because p₁.1 ∈ A while p₂.2 ∈ Aᶜ implies p₂.2 ∉ A.
uses
Finset.mem_filter,Finset.mem_product,Sym2.eq_iff,Prod.ext,Finset.mem_compl· intro p₁ hp₁ p₂ hp₂ h rw [Finset.mem_filter] at hp₁ hp₂ rw [Finset.mem_product] at hp₁ hp₂ rw [Sym2.eq_iff] at h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Prod.ext h1 h2 · exfalso have h_in_A : p₁.1 ∈ A := hp₁.1.1 have h_in_compl : p₂.2 ∈ Aᶜ := hp₂.1.2 rw [Finset.mem_compl] at h_in_compl rw [h1] at h_in_A exact h_in_compl h_in_A
The map is surjective: every cut edge arises from an adjacent pair in A × Aᶜ.
Given an edge e crossing the cut, by definition e ∈ G.edgeFinset and e = s(u, v) for some u ∈ A and v ∈ Aᶜ. The ordered pair (u, v) lies in A × Aᶜ, and since s(u, v) = e is an edge of G, u and v are adjacent. Thus (u, v) belongs to the domain, and its image is s(u, v) = e.
uses
Finset.mem_filter,Finset.mem_product,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet· intro e he rw [Finset.mem_filter] at he rcases he with ⟨he_edge, u, hu, v, hv, heq⟩ refine ⟨(u, v), ?_, heq.symm⟩ rw [Finset.mem_filter, Finset.mem_product] refine ⟨⟨hu, hv⟩, ?_⟩ rw [SimpleGraph.mem_edgeFinset] at he_edge rw [heq] at he_edge rw [SimpleGraph.mem_edgeSet] at he_edge exact he_edge
Finset.card_bij- Two finite sets have the same cardinality if there is a function between them that maps into the target set, is injective, and is surjective.
Finset.mem_filter- An element belongs to a filtered set {x ∈ s | p x} if and only if it belongs to s and satisfies the predicate p.
Finset.mem_product- A pair (a, b) belongs to the Cartesian product s ×ˢ t if and only if a ∈ s and b ∈ t.
SimpleGraph.mem_edgeFinset- An unordered pair belongs to the finite edge set of a graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- An unordered pair s(u, v) belongs to the edge set of a graph if and only if u and v are adjacent.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
Prod.ext- Two ordered pairs are equal if and only if their respective first and second components are equal.
Finset.mem_compl- An element belongs to the complement Aᶜ in a finite type if and only if it does not belong to A.
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.
/-- Ordered crossing pairs biject with crossing edges, so the two ways of counting a cut agree. -/theorem crossing_pairs_card_eq_crossing_edges_card {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) : ((A ×ˢ Aᶜ).filter (fun p : V × V => G.Adj p.1 p.2)).card = (G.edgeFinset.filter (fun e => ∃ u ∈ A, ∃ v ∈ (Aᶜ : Finset V), e = s(u, v))).card := by refine Finset.card_bij (fun p _ => s(p.1, p.2)) ?_ ?_ ?_ · intro p hp rw [Finset.mem_filter] at hp ⊢ rcases hp with ⟨hp_prod, hp_adj⟩ rw [Finset.mem_product] at hp_prod refine ⟨?_, p.1, hp_prod.1, p.2, hp_prod.2, rfl⟩ rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] exact hp_adj · intro p₁ hp₁ p₂ hp₂ h rw [Finset.mem_filter] at hp₁ hp₂ rw [Finset.mem_product] at hp₁ hp₂ rw [Sym2.eq_iff] at h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Prod.ext h1 h2 · exfalso have h_in_A : p₁.1 ∈ A := hp₁.1.1 have h_in_compl : p₂.2 ∈ Aᶜ := hp₂.1.2 rw [Finset.mem_compl] at h_in_compl rw [h1] at h_in_A exact h_in_compl h_in_A · intro e he rw [Finset.mem_filter] at he rcases he with ⟨he_edge, u, hu, v, hv, heq⟩ refine ⟨(u, v), ?_, heq.symm⟩ rw [Finset.mem_filter, Finset.mem_product] refine ⟨⟨hu, hv⟩, ?_⟩ rw [SimpleGraph.mem_edgeFinset] at he_edge rw [heq] at he_edge rw [SimpleGraph.mem_edgeSet] at he_edge exact he_edge