AFTD Auto-Formalizing Theoretical Domains

isMatching_verts_encard_le_two_mul

theoremverified

For any matching M in a graph G, the number of vertices in M is at most twice the number of edges in M.

Statement

theorem isMatching_verts_encard_le_two_mul {V : Type*} {G : SimpleGraph V} (M : G.Subgraph)
    (hM : M.IsMatching) : M.verts.encard ≤ 2 * M.edgeSet.encard
Source
step towards vertex_cover_num_le_two_mul_matching_num
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To bound the number of vertices in a matching M, the proof defines an endpoint map from M.edgeSet × Fin 2 to M.verts that selects one of the two endpoints of each edge. Because M is a matching, every vertex in M is incident to an edge, which makes this endpoint map surjective. The existence of an injective right inverse to this map implies that the cardinality of M.verts is at most the cardinality of M.edgeSet × Fin 2, which equals twice the number of edges.

  1. The two components of the chosen representative pair p of the edge x.1 are adjacent in M.

    The edge x.1 belongs to the edge set of M. Using `Quot.out_eq`, the canonical representative pair p = Quot.out x.1.val projects back to the edge x.1.val, showing that s(p.1, p.2) is in M.edgeSet, which by definition means p.1 and p.2 are adjacent in M.

    lines 5–8

    uses Quot.out_eq

        have h := x.1.2
        have hq := Quot.out_eq x.1.val
        rw [← hq] at h
        exact M.mem_edgeSet.mp h
  2. Every vertex v in M.verts is incident to an edge e in M.edgeSet.

    To prove surjectivity, let v be an arbitrary vertex in M.verts. Since M is a matching, every vertex in M has degree 1, so there exists a neighbor w adjacent to v in M. The unordered pair s(v, w) is then an edge in M.edgeSet, which we name e.

    lines 13–16

      intro ⟨v, hv⟩
      obtain ⟨w, hw, -⟩ := hM hv
      have he : s(v, w) ∈ M.edgeSet := M.mem_edgeSet.mpr hw
      let e : M.edgeSet := ⟨s(v, w), he⟩
  3. The canonical representative of e has v as either its first or its second endpoint.

    By `Quot.out_eq`, the unordered pair formed by the components of Quot.out e.val equals s(v, w). Rewriting with `Sym2.eq_iff` shows that either the first component is v and the second is w, or the first is w and the second is v.

    lines 17–20

    uses Quot.out_eq, Sym2.eq_iff

      have hq : Quot.mk (Sym2.Rel V) (Quot.out e.val) = s(v, w) := Quot.out_eq e.val
      have h_eq : s((Quot.out e.val).1, (Quot.out e.val).2) = s(v, w) := hq
      rw [Sym2.eq_iff] at h_eq
      rcases h_eq with ⟨h1, h2⟩ | ⟨h1, h2⟩
  4. The endpoint map is surjective onto M.verts.

    In the first case, the pair (e, 0) maps to the first component of the representative, which is v; in the second case, (e, 1) maps to the second component, which is v. In both branches, `Subtype.ext` verifies equality with v, proving that every vertex has a preimage under the endpoint map.

    lines 21–24

    uses Subtype.ext

      · use (e, 0)
        exact Subtype.ext h1
      · use (e, 1)
        exact Subtype.ext h2
  5. The cardinality of M.verts is at most the cardinality of M.edgeSet × Fin 2.

    By the surjectivity lemma `isMatching_verts_encard_le_two_mul_endpoint_surjective`, the endpoint map from M.edgeSet × Fin 2 to M.verts is surjective. By `Function.injective_surjInv`, its right inverse is injective. Therefore, by `ENat.card_le_card_of_injective`, the cardinality of M.verts is bounded by the cardinality of the product M.edgeSet × Fin 2.

    lines 29–31

    uses isMatching_verts_encard_le_two_mul_endpoint_surjective, ENat.card_le_card_of_injective, Function.injective_surjInv

      have hsurj := isMatching_verts_encard_le_two_mul_endpoint_surjective M hM
      have hle : ENat.card M.verts ≤ ENat.card (M.edgeSet × Fin 2) :=
        ENat.card_le_card_of_injective (Function.injective_surjInv hsurj)
  6. The number of vertices in M is at most twice the number of edges in M.

    By `ENat.card_prod`, the cardinality of the product splits into ENat.card M.edgeSet * ENat.card (Fin 2). The cardinality of Fin 2 is simplified to 2. Commuting the product with `mul_comm` and converting the subtype cardinalities to set extended cardinalities using `ENat.card_coe_set_eq` yields M.verts.encard ≤ 2 * M.edgeSet.encard.

    lines 32–35

    uses ENat.card_prod, mul_comm, ENat.card_coe_set_eq

      rw [ENat.card_prod] at hle
      have hFin2 : ENat.card (Fin 2) = 2 := by simp
      rw [hFin2, mul_comm, ENat.card_coe_set_eq, ENat.card_coe_set_eq] at hle
      exact hle
Quot.out_eq
The canonical representative `Quot.out q` of an element `q` in a quotient type projects back to `q`.
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).
Subtype.ext
Two subtype elements are equal if and only if their underlying values are equal.
isMatching_verts_encard_le_two_mul_endpoint_surjective
For any matching M, the map sending an edge and an index in {0, 1} to the corresponding endpoint is surjective onto M.verts.
ENat.card_le_card_of_injective
If there exists an injective function from type α to type β, then the extended natural cardinality of α is at most that of β.
Function.injective_surjInv
For any surjective function f, its chosen right inverse Function.surjInv f is injective.
ENat.card_prod
The extended natural cardinality of a Cartesian product α × β equals the product of their cardinalities.
mul_comm
Multiplication is commutative: a * b = b * a.
ENat.card_coe_set_eq
The extended natural cardinality of a subtype corresponding to a set s equals the set's extended cardinality s.encard.

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

noncomputable def isMatching_verts_encard_le_two_mul_endpoint {V : Type*} {G : SimpleGraph V} (M : G.Subgraph)    (x : M.edgeSet × Fin 2) : M.verts :=  let p := Quot.out x.1.val  have hAdj : M.Adj p.1 p.2 := by    have h := x.1.2    have hq := Quot.out_eq x.1.val    rw [← hq] at h    exact M.mem_edgeSet.mp h  Fin.cases ⟨p.1, M.edge_vert hAdj⟩ (fun _ => ⟨p.2, M.edge_vert hAdj.symm⟩) x.2lemma isMatching_verts_encard_le_two_mul_endpoint_surjective {V : Type*} {G : SimpleGraph V} (M : G.Subgraph)    (hM : M.IsMatching) : Function.Surjective (isMatching_verts_encard_le_two_mul_endpoint M) := by  intro ⟨v, hv⟩  obtain ⟨w, hw, -⟩ := hM hv  have he : s(v, w) ∈ M.edgeSet := M.mem_edgeSet.mpr hw  let e : M.edgeSet := ⟨s(v, w), he⟩  have hq : Quot.mk (Sym2.Rel V) (Quot.out e.val) = s(v, w) := Quot.out_eq e.val  have h_eq : s((Quot.out e.val).1, (Quot.out e.val).2) = s(v, w) := hq  rw [Sym2.eq_iff] at h_eq  rcases h_eq with ⟨h1, h2⟩ | ⟨h1, h2⟩  · use (e, 0)    exact Subtype.ext h1  · use (e, 1)    exact Subtype.ext h2/-- In any simple graph, the number of vertices in a matching M is at most twice the number of edges in M. -/theorem isMatching_verts_encard_le_two_mul {V : Type*} {G : SimpleGraph V} (M : G.Subgraph)    (hM : M.IsMatching) : M.verts.encard ≤ 2 * M.edgeSet.encard := by  have hsurj := isMatching_verts_encard_le_two_mul_endpoint_surjective M hM  have hle : ENat.card M.verts ≤ ENat.card (M.edgeSet × Fin 2) :=    ENat.card_le_card_of_injective (Function.injective_surjInv hsurj)  rw [ENat.card_prod] at hle  have hFin2 : ENat.card (Fin 2) = 2 := by simp  rw [hFin2, mul_comm, ENat.card_coe_set_eq, ENat.card_coe_set_eq] at hle  exact hle
See it in the graphDiscuss this resultChallenge it