AFTD Auto-Formalizing Theoretical Domains

crossing_pairs_card_eq_crossing_edges_card

theoremverified

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

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.

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

    line 6

    uses Finset.card_bij

      refine Finset.card_bij (fun p _ => s(p.1, p.2)) ?_ ?_ ?_
  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ᶜ.

    lines 7–13

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

    lines 14–25

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

    lines 26–35

    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

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