AFTD Auto-Formalizing Theoretical Domains

graph_matching_num_two_mul_le_card

theoremverified

In any finite simple graph G on vertex set V, twice the matching number is at most the number of vertices, 2 * graph_matching_num G ≤ |V|.

Statement

theorem graph_matching_num_two_mul_le_card {V : Type*} [Fintype V] (G : SimpleGraph V) :
    2 * graph_matching_num G ≤ (Fintype.card V : ℕ∞)
Source
folklore
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.

Read back from the Lean

For every finite type V and every simple graph G on V, twice the matching number of G (graph_matching_num G) is less than or equal to the cardinality of V (coerced to ℕ∞).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem states that in any finite graph G, twice the matching number is at most the total number of vertices: 2 * ν(G) ≤ |V|. The argument shows that for any matching M, there is an injective map from Fin 2 × M.edgeSet to V sending each edge to its two endpoints. Because each vertex in a matching belongs to at most one matching edge and the two endpoints of an edge are distinct, this map is injective, giving 2 * |M.edgeSet| ≤ |V|; taking the supremum over all matchings M completes the proof.

  1. Every edge in a subgraph M can be written as an unordered pair s(u, v) whose endpoints u and v are adjacent in M.

    Unpacking the edge subtype e and applying induction on Sym2 via `Sym2.ind`, any edge is represented as s(u, v). Its adjacency in M follows directly from the membership hypothesis of the edge in M.edgeSet.

    lines 4–7

    uses Sym2.ind

      obtain ⟨e_val, he⟩ := e
      induction e_val using Sym2.ind with
      | h u v =>
        exact ⟨(u, v), rfl, he⟩
  2. For any edge e in a matching M, applying the matching map `toEdge` to its first endpoint recovers e.

    By `toEdge_eq_of_adj`, any matched vertex adjacent to another vertex in M has that edge as its unique incident edge in M. Passing to the underlying values and using `Subtype.ext` shows this matches e.

    lines 23–26

    uses graph_matching_num_two_mul_le_card_edgeEndpoints_spec, Subtype.ext, congr_arg, Subtype.val

      have := hM.toEdge_eq_of_adj (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).2
      apply Subtype.ext
      have h_val := congr_arg Subtype.val this
      exact h_val.trans (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).1.symm
  3. For any edge e in a matching M, applying `toEdge` to its second endpoint recovers e.

    By symmetry of adjacency, the second endpoint is adjacent to the first in M. Applying `toEdge` gives the edge s(v, u), which equals s(u, v) = e by `Sym2.eq_swap`.

    lines 32–35

    uses graph_matching_num_two_mul_le_card_edgeEndpoints_spec, Subtype.ext, congr_arg, Subtype.val, Sym2.eq_swap

      have := hM.toEdge_eq_of_adj (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).2.symm
      apply Subtype.ext
      have h_val := congr_arg Subtype.val this
      exact h_val.trans (Sym2.eq_swap.trans (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).1.symm)
  4. For every indexed edge in `Fin 2 × M.edgeSet`, the selected endpoint belongs to M.verts.

    Unfolding the definition of `endpoint`, the vertex is either the first or second endpoint of the edge. Since the two endpoints are adjacent in M, both belong to M.verts.

    lines 45–48

    uses graph_matching_num_two_mul_le_card_endpoint, graph_matching_num_two_mul_le_card_edgeEndpoints_spec

      dsimp [graph_matching_num_two_mul_le_card_endpoint]
      split_ifs
      · exact (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M p.2).2.fst_mem
      · exact (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M p.2).2.snd_mem
  5. Applying `toEdge` to the i-th endpoint of an edge e recovers e for any index i.

    Case-splitting on whether i = 0 or i = 1 reduces directly to `toEdge_endpoint1` and `toEdge_endpoint2` respectively.

    lines 54–57

    uses graph_matching_num_two_mul_le_card_endpoint, graph_matching_num_two_mul_le_card_toEdge_endpoint1, graph_matching_num_two_mul_le_card_toEdge_endpoint2

      dsimp [graph_matching_num_two_mul_le_card_endpoint]
      split_ifs
      · exact graph_matching_num_two_mul_le_card_toEdge_endpoint1 hM p.2
      · exact graph_matching_num_two_mul_le_card_toEdge_endpoint2 hM p.2
  6. Any two distinct elements of Fin 2 are either 0 and 1, or 1 and 0.

    There are only two elements in Fin 2, so exhaustively checking the finite possibilities confirms that unequal elements must be 0 and 1 in some order.

    lines 61–62

      revert i j
      decide
  7. If two indexed edges map to the same vertex, they must share the same edge component.

    If f(p₁) = f(p₂) as vertices, applying `toEdge` to both sides yields p₁.2 = toEdge(f(p₁)) = toEdge(f(p₂)) = p₂.2, because a matched vertex belongs to a unique edge in the matching.

    lines 67–76

    uses graph_matching_num_two_mul_le_card_toEdge_endpoint, graph_matching_num_two_mul_le_card_endpoint_mem_verts, Subtype.ext

      intro p₁ p₂ h
      have he : p₁.2 = p₂.2 := by
        have h1 := graph_matching_num_two_mul_le_card_toEdge_endpoint hM p₁
        have h2 := graph_matching_num_two_mul_le_card_toEdge_endpoint hM p₂
        have h_eq : (⟨graph_matching_num_two_mul_le_card_endpoint M p₁,
                       graph_matching_num_two_mul_le_card_endpoint_mem_verts M p₁⟩ : M.verts) =
                    ⟨graph_matching_num_two_mul_le_card_endpoint M p₂,
                     graph_matching_num_two_mul_le_card_endpoint_mem_verts M p₂⟩ := Subtype.ext h
        rw [h_eq] at h1
        exact h1.symm.trans h2
  8. If two indexed edges map to the same vertex, their index components also match, proving the endpoint map is injective.

    If p₁.1 ≠ p₂.1, then one index is 0 and the other is 1. Since p₁.2 = p₂.2, this would mean the two endpoints of that same edge are equal to each other. But adjacent vertices in a simple graph are always distinct, giving a contradiction. Hence p₁.1 = p₂.1, and `Prod.ext` gives p₁ = p₂.

    lines 77–102

    uses graph_matching_num_two_mul_le_card_fin2_ne_cases, if_pos, if_neg, graph_matching_num_two_mul_le_card_edgeEndpoints_spec, Prod.ext

      have hi : p₁.1 = p₂.1 := by
        by_contra hne
        rcases graph_matching_num_two_mul_le_card_fin2_ne_cases hne with ⟨h0, h1⟩ | ⟨h1, h0⟩
        · exfalso
          have hp1 : graph_matching_num_two_mul_le_card_endpoint M p₁ =
              (graph_matching_num_two_mul_le_card_edgeEndpoints M p₁.2).1 := by
            dsimp [graph_matching_num_two_mul_le_card_endpoint]
            rw [if_pos h0]
          have hp2 : graph_matching_num_two_mul_le_card_endpoint M p₂ =
              (graph_matching_num_two_mul_le_card_edgeEndpoints M p₂.2).2 := by
            dsimp [graph_matching_num_two_mul_le_card_endpoint]
            rw [if_neg (by rw [h1]; decide)]
          rw [hp1, hp2, he] at h
          exact (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M p₂.2).2.ne h
        · exfalso
          have hp1 : graph_matching_num_two_mul_le_card_endpoint M p₁ =
              (graph_matching_num_two_mul_le_card_edgeEndpoints M p₁.2).2 := by
            dsimp [graph_matching_num_two_mul_le_card_endpoint]
            rw [if_neg (by rw [h1]; decide)]
          have hp2 : graph_matching_num_two_mul_le_card_endpoint M p₂ =
              (graph_matching_num_two_mul_le_card_edgeEndpoints M p₂.2).1 := by
            dsimp [graph_matching_num_two_mul_le_card_endpoint]
            rw [if_pos h0]
          rw [hp1, hp2, he] at h
          exact (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M p₂.2).2.symm.ne h
      exact Prod.ext hi he
  9. Bounding 2 * graph_matching_num G ≤ |V| reduces to showing 2 * |M.edgeSet| ≤ |V| for every matching M.

    The matching number is defined as the supremum of |M.edgeSet| over all matchings M. Distributing multiplication by 2 over the supremum via `ENat.mul_iSup` and using `iSup_le`, it suffices to bound each matching individually.

    lines 107–111

    uses ENat.mul_iSup, iSup_le

      dsimp [graph_matching_num]
      rw [ENat.mul_iSup]
      refine iSup_le fun M ↦ ?_
      rw [ENat.mul_iSup]
      refine iSup_le fun hM ↦ ?_
  10. For every matching M, 2 * |M.edgeSet| ≤ |V|, concluding the theorem.

    Because the endpoint map `Fin 2 × M.edgeSet → V` is injective, the cardinality of `Fin 2 × M.edgeSet` is at most |V|. Since |Fin 2 × M.edgeSet| = 2 * |M.edgeSet|, this establishes 2 * |M.edgeSet| ≤ |V|.

    lines 112–118

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

      have hinj := graph_matching_num_two_mul_le_card_endpoint_injective hM
      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
Sym2.ind
To prove a statement for all unordered pairs in `Sym2 α`, it suffices to prove it for pairs of the form `s(x, y)`.
graph_matching_num_two_mul_le_card_edgeEndpoints_spec
The chosen pair of vertices for an edge `e` in a subgraph `M` satisfies `e = s(u, v)` and `u` is adjacent to `v` in `M`.
Subtype.ext
Two terms of a subtype are equal if and only if their underlying values are equal.
congr_arg
Equality is preserved under function application: if `a = b` then `f a = f b`.
Subtype.val
Extracts the underlying value of a subtype term.
Sym2.eq_swap
The unordered pair `s(a, b)` is identical to `s(b, a)`.
graph_matching_num_two_mul_le_card_endpoint
Maps an indexed edge `(i, e) ∈ Fin 2 × M.edgeSet` to the first endpoint of `e` if `i = 0`, and the second endpoint otherwise.
graph_matching_num_two_mul_le_card_toEdge_endpoint1
Applying the matching map `toEdge` to the first chosen endpoint of an edge `e` returns `e`.
graph_matching_num_two_mul_le_card_toEdge_endpoint2
Applying the matching map `toEdge` to the second chosen endpoint of an edge `e` returns `e`.
graph_matching_num_two_mul_le_card_toEdge_endpoint
Applying the matching map `toEdge` to either endpoint of an edge `e` returns `e`.
graph_matching_num_two_mul_le_card_endpoint_mem_verts
The endpoint chosen for any indexed edge in `Fin 2 × M.edgeSet` is a vertex of `M`.
graph_matching_num_two_mul_le_card_fin2_ne_cases
Two distinct elements of `Fin 2` must be 0 and 1 in one order or the other.
if_pos
An `if-then-else` expression reduces to the `then` branch when the condition is true.
if_neg
An `if-then-else` expression reduces to the `else` branch when the condition is false.
Prod.ext
Two ordered pairs are equal if their first components are equal and their second components are equal.
ENat.mul_iSup
Multiplication by a scalar distributes over an arbitrary supremum in `ℕ∞`.
iSup_le
A supremum is at most `a` if and only if every element in the family is at most `a`.
graph_matching_num_two_mul_le_card_endpoint_injective
The endpoint assignment map from `Fin 2 × M.edgeSet` to `V` is injective for any matching `M`.
ENat.card_le_card_of_injective
An injection from `α` to `β` implies `ENat.card α ≤ ENat.card β`.
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 the subtype coerced from a set `s` equals `s.encard`.
ENat.card_eq_coe_fintype_card
For a finite type, `ENat.card` equals the coerced `Fintype.card`.

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

lemma graph_matching_num_two_mul_le_card_endpoints_of_mem_edgeSet {V : Type*} {G : SimpleGraph V}    (M : G.Subgraph) (e : M.edgeSet) :    ∃ p : V × V, e.1 = s(p.1, p.2) ∧ M.Adj p.1 p.2 := by  obtain ⟨e_val, he⟩ := e  induction e_val using Sym2.ind with  | h u v =>    exact ⟨(u, v), rfl, he⟩noncomputable def graph_matching_num_two_mul_le_card_edgeEndpoints {V : Type*} {G : SimpleGraph V}    (M : G.Subgraph) (e : M.edgeSet) : V × V :=  Classical.choose (graph_matching_num_two_mul_le_card_endpoints_of_mem_edgeSet M e)lemma graph_matching_num_two_mul_le_card_edgeEndpoints_spec {V : Type*} {G : SimpleGraph V}    (M : G.Subgraph) (e : M.edgeSet) :    e.1 = s((graph_matching_num_two_mul_le_card_edgeEndpoints M e).1, (graph_matching_num_two_mul_le_card_edgeEndpoints M e).2) ∧    M.Adj (graph_matching_num_two_mul_le_card_edgeEndpoints M e).1 (graph_matching_num_two_mul_le_card_edgeEndpoints M e).2 :=  Classical.choose_spec (graph_matching_num_two_mul_le_card_endpoints_of_mem_edgeSet M e)lemma graph_matching_num_two_mul_le_card_toEdge_endpoint1 {V : Type*} {G : SimpleGraph V}    {M : G.Subgraph} (hM : M.IsMatching) (e : M.edgeSet) :    hM.toEdge ⟨(graph_matching_num_two_mul_le_card_edgeEndpoints M e).1,      (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).2.fst_mem⟩ = e := by  have := hM.toEdge_eq_of_adj (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).2  apply Subtype.ext  have h_val := congr_arg Subtype.val this  exact h_val.trans (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).1.symmlemma graph_matching_num_two_mul_le_card_toEdge_endpoint2 {V : Type*} {G : SimpleGraph V}    {M : G.Subgraph} (hM : M.IsMatching) (e : M.edgeSet) :    hM.toEdge ⟨(graph_matching_num_two_mul_le_card_edgeEndpoints M e).2,      (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).2.snd_mem⟩ = e := by  have := hM.toEdge_eq_of_adj (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).2.symm  apply Subtype.ext  have h_val := congr_arg Subtype.val this  exact h_val.trans (Sym2.eq_swap.trans (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M e).1.symm)noncomputable def graph_matching_num_two_mul_le_card_endpoint {V : Type*} {G : SimpleGraph V}    (M : G.Subgraph) (p : Fin 2 × M.edgeSet) : V :=  if p.1 = 0 then (graph_matching_num_two_mul_le_card_edgeEndpoints M p.2).1  else (graph_matching_num_two_mul_le_card_edgeEndpoints M p.2).2lemma graph_matching_num_two_mul_le_card_endpoint_mem_verts {V : Type*} {G : SimpleGraph V}    (M : G.Subgraph) (p : Fin 2 × M.edgeSet) :    graph_matching_num_two_mul_le_card_endpoint M p ∈ M.verts := by  dsimp [graph_matching_num_two_mul_le_card_endpoint]  split_ifs  · exact (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M p.2).2.fst_mem  · exact (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M p.2).2.snd_memlemma graph_matching_num_two_mul_le_card_toEdge_endpoint {V : Type*} {G : SimpleGraph V}    {M : G.Subgraph} (hM : M.IsMatching) (p : Fin 2 × M.edgeSet) :    hM.toEdge ⟨graph_matching_num_two_mul_le_card_endpoint M p,      graph_matching_num_two_mul_le_card_endpoint_mem_verts M p⟩ = p.2 := by  dsimp [graph_matching_num_two_mul_le_card_endpoint]  split_ifs  · exact graph_matching_num_two_mul_le_card_toEdge_endpoint1 hM p.2  · exact graph_matching_num_two_mul_le_card_toEdge_endpoint2 hM p.2lemma graph_matching_num_two_mul_le_card_fin2_ne_cases {i j : Fin 2} (h : i ≠ j) :    (i = 0 ∧ j = 1) ∨ (i = 1 ∧ j = 0) := by  revert i j  decidelemma graph_matching_num_two_mul_le_card_endpoint_injective {V : Type*} {G : SimpleGraph V}    {M : G.Subgraph} (hM : M.IsMatching) :    Function.Injective (graph_matching_num_two_mul_le_card_endpoint M) := by  intro p₁ p₂ h  have he : p₁.2 = p₂.2 := by    have h1 := graph_matching_num_two_mul_le_card_toEdge_endpoint hM p₁    have h2 := graph_matching_num_two_mul_le_card_toEdge_endpoint hM p₂    have h_eq : (⟨graph_matching_num_two_mul_le_card_endpoint M p₁,                   graph_matching_num_two_mul_le_card_endpoint_mem_verts M p₁⟩ : M.verts) =                ⟨graph_matching_num_two_mul_le_card_endpoint M p₂,                 graph_matching_num_two_mul_le_card_endpoint_mem_verts M p₂⟩ := Subtype.ext h    rw [h_eq] at h1    exact h1.symm.trans h2  have hi : p₁.1 = p₂.1 := by    by_contra hne    rcases graph_matching_num_two_mul_le_card_fin2_ne_cases hne with ⟨h0, h1⟩ | ⟨h1, h0⟩    · exfalso      have hp1 : graph_matching_num_two_mul_le_card_endpoint M p₁ =          (graph_matching_num_two_mul_le_card_edgeEndpoints M p₁.2).1 := by        dsimp [graph_matching_num_two_mul_le_card_endpoint]        rw [if_pos h0]      have hp2 : graph_matching_num_two_mul_le_card_endpoint M p₂ =          (graph_matching_num_two_mul_le_card_edgeEndpoints M p₂.2).2 := by        dsimp [graph_matching_num_two_mul_le_card_endpoint]        rw [if_neg (by rw [h1]; decide)]      rw [hp1, hp2, he] at h      exact (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M p₂.2).2.ne h    · exfalso      have hp1 : graph_matching_num_two_mul_le_card_endpoint M p₁ =          (graph_matching_num_two_mul_le_card_edgeEndpoints M p₁.2).2 := by        dsimp [graph_matching_num_two_mul_le_card_endpoint]        rw [if_neg (by rw [h1]; decide)]      have hp2 : graph_matching_num_two_mul_le_card_endpoint M p₂ =          (graph_matching_num_two_mul_le_card_edgeEndpoints M p₂.2).1 := by        dsimp [graph_matching_num_two_mul_le_card_endpoint]        rw [if_pos h0]      rw [hp1, hp2, he] at h      exact (graph_matching_num_two_mul_le_card_edgeEndpoints_spec M p₂.2).2.symm.ne h  exact Prod.ext hi he/-- Twice the matching number is at most the number of vertices in a finite graph. -/theorem graph_matching_num_two_mul_le_card {V : Type*} [Fintype V] (G : SimpleGraph V) :    2 * graph_matching_num G ≤ (Fintype.card V : ℕ∞) := by  dsimp [graph_matching_num]  rw [ENat.mul_iSup]  refine iSup_le fun M ↦ ?_  rw [ENat.mul_iSup]  refine iSup_le fun hM ↦ ?_  have hinj := graph_matching_num_two_mul_le_card_endpoint_injective hM  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