AFTD Auto-Formalizing Theoretical Domains

matching_two_mul_encard_le_card

theoremverified

For any matching M in a finite graph G, twice its edge cardinality is at most the number of vertices.

Statement

theorem matching_two_mul_encard_le_card {V : Type*} [Fintype V] (G : SimpleGraph V) (M : G.Subgraph)
    (h : M.IsMatching) : 2 * M.edgeSet.encard ≤ (Fintype.card V : ℕ∞)
Source
step towards graph_matching_num_two_mul_le_card
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by constructing an injection f from Fin 2 × M.edgeSet into the vertex set V, which immediately yields the cardinality bound 2 * |M| ≤ |V|. The map f associates each pair (i, e) with the first endpoint of e if i = 0 and the second endpoint if i = 1. To prove injectivity, notice that each vertex in a matching belongs to at most one matching edge, so equal images force the edges to coincide. Furthermore, the two endpoints of an edge in a simple graph are adjacent and therefore distinct, preventing the two indices from differing on the same edge.

  1. Any two distinct elements of Fin 2 are 0 and 1 in some order. automation

    For a, b : Fin 2 with a ≠ b, finite case exhaustion using the decide tactic confirms that either a = 0 ∧ b = 1 or a = 1 ∧ b = 0.

    lines 5–6

      revert a b
      decide
  2. The representative endpoints of any edge in M are adjacent in M.

    The edge e belongs to M.edgeSet by subtype definition. The quotient projection of Quot.out e.1 is e by Quot.out_eq, so rewriting by this identity shows that the first and second components of Quot.out e.1 are adjacent in M.

    lines 14–16

    uses Quot.out_eq

      have he := e.2
      have hq := Quot.out_eq e.1
      rwa [← hq] at he
  3. The vertex selected by f(M, p) belongs to the vertex set of M.

    Unfolding f, if p.1 = 0, the function selects the first endpoint of p.2, which belongs to M.verts by the adjacency lemma matching_two_mul_encard_le_card_adj. If p.1 ≠ 0, it selects the second endpoint, which likewise belongs to M.verts.

    lines 20–23

    uses matching_two_mul_encard_le_card_adj

      dsimp [matching_two_mul_encard_le_card_f]
      split_ifs
      · exact (matching_two_mul_encard_le_card_adj M p.2).fst_mem
      · exact (matching_two_mul_encard_le_card_adj M p.2).snd_mem
  4. When p.1 = 0, the unique matching edge incident to f(M, p) is p.2.

    When p.1 = 0, f(M, p) is the first endpoint of p.2. Since M is a matching and the endpoints are adjacent by matching_two_mul_encard_le_card_adj, the unique incident edge in M is the unordered pair of these endpoints. Using Subtype.ext, congr_arg, and Subtype.val, together with Quot.out_eq, this edge is identified with p.2.

    lines 28–35

    uses matching_two_mul_encard_le_card_adj, Subtype.ext, congr_arg, Subtype.val, Quot.out_eq

      dsimp [matching_two_mul_encard_le_card_f]
      split_ifs with h0
      · have hadj := matching_two_mul_encard_le_card_adj M p.2
        have ht := h.toEdge_eq_of_adj hadj
        apply Subtype.ext
        have ht' : ((h.toEdge ⟨(Quot.out p.2.1).1, hadj.fst_mem⟩ : M.edgeSet) : Sym2 V) =
            s((Quot.out p.2.1).1, (Quot.out p.2.1).2) := congr_arg Subtype.val ht
        exact ht'.trans (Quot.out_eq p.2.1)
  5. When p.1 ≠ 0, the unique matching edge incident to f(M, p) is also p.2.

    When p.1 ≠ 0, f(M, p) is the second endpoint of p.2. By symmetry of adjacency, the second endpoint is adjacent to the first in M. The matching property assigns the incident edge as the unordered pair with endpoints reversed. Swapping them with Sym2.eq_swap and applying Quot.out_eq recovers p.2.

    lines 36–42

    uses matching_two_mul_encard_le_card_adj, Subtype.ext, congr_arg, Subtype.val, Sym2.eq_swap, Quot.out_eq

      · have hadj := matching_two_mul_encard_le_card_adj M p.2
        have ht := h.toEdge_eq_of_adj hadj.symm
        apply Subtype.ext
        have ht' : ((h.toEdge ⟨(Quot.out p.2.1).2, hadj.snd_mem⟩ : M.edgeSet) : Sym2 V) =
            s((Quot.out p.2.1).2, (Quot.out p.2.1).1) := congr_arg Subtype.val ht
        have ht'' := ht'.trans Sym2.eq_swap
        exact ht''.trans (Quot.out_eq p.2.1)
  6. If f(M, p1) = f(M, p2), then their edge components are equal: p1.2 = p2.2.

    Equality of the mapped vertices f(M, p1) = f(M, p2) implies equality as elements of M.verts via Subtype.ext. Applying h.toEdge using congr_arg and simplifying each side with matching_two_mul_encard_le_card_toEdge proves p1.2 = p2.2.

    lines 46–53

    uses Subtype.ext, congr_arg, matching_two_mul_encard_le_card_toEdge

      intro p1 p2 hp
      have h_edge : p1.2 = p2.2 := by
        have h_v : (⟨matching_two_mul_encard_le_card_f M p1, matching_two_mul_encard_le_card_mem M p1⟩ : M.verts) =
            ⟨matching_two_mul_encard_le_card_f M p2, matching_two_mul_encard_le_card_mem M p2⟩ :=
          Subtype.ext hp
        have h_to := congr_arg h.toEdge h_v
        rw [matching_two_mul_encard_le_card_toEdge h p1, matching_two_mul_encard_le_card_toEdge h p2] at h_to
        exact h_to
  7. If f(M, p1) = f(M, p2), then their index components are equal (p1.1 = p2.1), so p1 = p2.

    Assuming for contradiction that p1.1 ≠ p2.1, lemma matching_two_mul_encard_le_card_fin2_cases gives two cases: (0, 1) or (1, 0). Simplifying f using if_pos and if_neg and using p1.2 = p2.2 forces the two endpoints of p2.2 to be equal. But adjacent vertices in a simple graph cannot be equal (matching_two_mul_encard_le_card_adj), yielding a contradiction. Thus p1.1 = p2.1, and Prod.ext concludes p1 = p2.

    lines 54–69

    uses matching_two_mul_encard_le_card_fin2_cases, if_pos, if_neg, matching_two_mul_encard_le_card_adj, Prod.ext

      have h_fin : p1.1 = p2.1 := by
        by_contra hne
        have hcases := matching_two_mul_encard_le_card_fin2_cases p1.1 p2.1 hne
        rcases hcases with ⟨h1, h2⟩ | ⟨h1, h2⟩
        · dsimp [matching_two_mul_encard_le_card_f] at hp
          rw [h1, h2] at hp
          rw [if_pos rfl, if_neg (by decide)] at hp
          rw [h_edge] at hp
          exact (matching_two_mul_encard_le_card_adj M p2.2).ne hp
        · dsimp [matching_two_mul_encard_le_card_f] at hp
          rw [h1, h2] at hp
          rw [if_neg (by decide), if_pos rfl] at hp
          rw [h_edge] at hp
          have hadj := matching_two_mul_encard_le_card_adj M p2.2
          exact hadj.symm.ne hp
      exact Prod.ext h_fin h_edge
  8. Twice the edge cardinality of M is at most the vertex cardinality of V: 2 * |M.edgeSet| ≤ |V|.

    By matching_two_mul_encard_le_card_injective, f is injective, so ENat.card_le_card_of_injective bounds the cardinality of Fin 2 × M.edgeSet by that of V. Applying ENat.card_prod and ENat.card_coe_set_eq evaluates the product cardinality as 2 * M.edgeSet.encard. Finally, ENat.card_eq_coe_fintype_card rewrites the bound as the cardinality of V, completing the proof.

    lines 74–80

    uses matching_two_mul_encard_le_card_injective, ENat.card_le_card_of_injective, ENat.card_prod, ENat.card_coe_set_eq, ENat.card_eq_coe_fintype_card

      have hinj := matching_two_mul_encard_le_card_injective h
      have hcard := ENat.card_le_card_of_injective hinj
      have hprod : ENat.card (Fin 2 × M.edgeSet) = 2 * M.edgeSet.encard := by
        rw [ENat.card_prod, ENat.card_coe_set_eq]
        simp
      rw [ENat.card_eq_coe_fintype_card (α := V)] at hcard
      exact hprod ▸ hcard
matching_two_mul_encard_le_card_fin2_cases
Any two distinct elements of {0, 1} are either 0 and 1 or 1 and 0.
Quot.out_eq
Projecting the canonical representative Quot.out q back to the quotient yields the original quotient element q.
matching_two_mul_encard_le_card_adj
The two representative endpoints chosen by Quot.out for any edge of subgraph M are adjacent in M.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
congr_arg
Applying a function to equal inputs produces equal outputs.
Subtype.val
The projection extracting the underlying value from a subtype element.
Sym2.eq_swap
An unordered pair is symmetric with respect to swapping its elements: s(a, b) = s(b, a).
matching_two_mul_encard_le_card_toEdge
For any matching M and pair p = (i, e), the unique edge of M incident to the vertex f(M, p) is e.
if_pos
If a condition c is true, then (if c then t else e) evaluates to t.
if_neg
If a condition c is false, then (if c then t else e) evaluates to e.
Prod.ext
Two ordered pairs are equal if their first components and second components are respectively equal.
matching_two_mul_encard_le_card_injective
For any matching M, the map f from Fin 2 × M.edgeSet to V is injective.
ENat.card_le_card_of_injective
An injective map between types implies that the cardinality of the domain is at most that of the codomain.
ENat.card_prod
The cardinality of a product type is the product of the cardinalities of its factor types.
ENat.card_coe_set_eq
The cardinality of a set coerced to a type equals its extended natural cardinality encard.
ENat.card_eq_coe_fintype_card
For a finite type, its cardinality as an extended natural number equals its cardinality as a natural number.

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

open Sym2lemma matching_two_mul_encard_le_card_fin2_cases (a b : Fin 2) (h : a ≠ b) :    (a = 0 ∧ b = 1) ∨ (a = 1 ∧ b = 0) := by  revert a b  decidenoncomputable def matching_two_mul_encard_le_card_f {V : Type*} {G : SimpleGraph V} (M : G.Subgraph)    (p : Fin 2 × M.edgeSet) : V :=  if p.1 = 0 then (Quot.out p.2.1).1 else (Quot.out p.2.1).2lemma matching_two_mul_encard_le_card_adj {V : Type*} {G : SimpleGraph V} (M : G.Subgraph) (e : M.edgeSet) :    M.Adj (Quot.out e.1).1 (Quot.out e.1).2 := by  have he := e.2  have hq := Quot.out_eq e.1  rwa [← hq] at helemma matching_two_mul_encard_le_card_mem {V : Type*} {G : SimpleGraph V} (M : G.Subgraph)    (p : Fin 2 × M.edgeSet) : matching_two_mul_encard_le_card_f M p ∈ M.verts := by  dsimp [matching_two_mul_encard_le_card_f]  split_ifs  · exact (matching_two_mul_encard_le_card_adj M p.2).fst_mem  · exact (matching_two_mul_encard_le_card_adj M p.2).snd_memlemma matching_two_mul_encard_le_card_toEdge {V : Type*} {G : SimpleGraph V} {M : G.Subgraph}    (h : M.IsMatching) (p : Fin 2 × M.edgeSet) :    h.toEdge ⟨matching_two_mul_encard_le_card_f M p, matching_two_mul_encard_le_card_mem M p⟩ = p.2 := by  dsimp [matching_two_mul_encard_le_card_f]  split_ifs with h0  · have hadj := matching_two_mul_encard_le_card_adj M p.2    have ht := h.toEdge_eq_of_adj hadj    apply Subtype.ext    have ht' : ((h.toEdge ⟨(Quot.out p.2.1).1, hadj.fst_mem⟩ : M.edgeSet) : Sym2 V) =        s((Quot.out p.2.1).1, (Quot.out p.2.1).2) := congr_arg Subtype.val ht    exact ht'.trans (Quot.out_eq p.2.1)  · have hadj := matching_two_mul_encard_le_card_adj M p.2    have ht := h.toEdge_eq_of_adj hadj.symm    apply Subtype.ext    have ht' : ((h.toEdge ⟨(Quot.out p.2.1).2, hadj.snd_mem⟩ : M.edgeSet) : Sym2 V) =        s((Quot.out p.2.1).2, (Quot.out p.2.1).1) := congr_arg Subtype.val ht    have ht'' := ht'.trans Sym2.eq_swap    exact ht''.trans (Quot.out_eq p.2.1)theorem matching_two_mul_encard_le_card_injective {V : Type*} {G : SimpleGraph V} {M : G.Subgraph}    (h : M.IsMatching) : Function.Injective (matching_two_mul_encard_le_card_f M) := by  intro p1 p2 hp  have h_edge : p1.2 = p2.2 := by    have h_v : (⟨matching_two_mul_encard_le_card_f M p1, matching_two_mul_encard_le_card_mem M p1⟩ : M.verts) =        ⟨matching_two_mul_encard_le_card_f M p2, matching_two_mul_encard_le_card_mem M p2⟩ :=      Subtype.ext hp    have h_to := congr_arg h.toEdge h_v    rw [matching_two_mul_encard_le_card_toEdge h p1, matching_two_mul_encard_le_card_toEdge h p2] at h_to    exact h_to  have h_fin : p1.1 = p2.1 := by    by_contra hne    have hcases := matching_two_mul_encard_le_card_fin2_cases p1.1 p2.1 hne    rcases hcases with ⟨h1, h2⟩ | ⟨h1, h2⟩    · dsimp [matching_two_mul_encard_le_card_f] at hp      rw [h1, h2] at hp      rw [if_pos rfl, if_neg (by decide)] at hp      rw [h_edge] at hp      exact (matching_two_mul_encard_le_card_adj M p2.2).ne hp    · dsimp [matching_two_mul_encard_le_card_f] at hp      rw [h1, h2] at hp      rw [if_neg (by decide), if_pos rfl] at hp      rw [h_edge] at hp      have hadj := matching_two_mul_encard_le_card_adj M p2.2      exact hadj.symm.ne hp  exact Prod.ext h_fin h_edge/-- For any matching M in a finite graph G, twice its edge cardinality is at most the number of vertices. -/theorem matching_two_mul_encard_le_card {V : Type*} [Fintype V] (G : SimpleGraph V) (M : G.Subgraph)    (h : M.IsMatching) : 2 * M.edgeSet.encard ≤ (Fintype.card V : ℕ∞) := by  have hinj := matching_two_mul_encard_le_card_injective h  have hcard := ENat.card_le_card_of_injective hinj  have hprod : ENat.card (Fin 2 × M.edgeSet) = 2 * M.edgeSet.encard := by    rw [ENat.card_prod, ENat.card_coe_set_eq]    simp  rw [ENat.card_eq_coe_fintype_card (α := V)] at hcard  exact hprod ▸ hcard
See it in the graphDiscuss this resultChallenge it