graph_matching_num_two_mul_le_card
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.
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.
uses
Sym2.indobtain ⟨e_val, he⟩ := e induction e_val using Sym2.ind with | h u v => exact ⟨(u, v), rfl, he⟩
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.
uses
graph_matching_num_two_mul_le_card_edgeEndpoints_spec,Subtype.ext,congr_arg,Subtype.valhave := 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
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`.
uses
graph_matching_num_two_mul_le_card_edgeEndpoints_spec,Subtype.ext,congr_arg,Subtype.val,Sym2.eq_swaphave := 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)
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.
uses
graph_matching_num_two_mul_le_card_endpoint,graph_matching_num_two_mul_le_card_edgeEndpoints_specdsimp [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
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.
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_endpoint2dsimp [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
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.
revert i j decideIf 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.
uses
graph_matching_num_two_mul_le_card_toEdge_endpoint,graph_matching_num_two_mul_le_card_endpoint_mem_verts,Subtype.extintro 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
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₂.
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.exthave 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
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.
uses
ENat.mul_iSup,iSup_ledsimp [graph_matching_num] rw [ENat.mul_iSup] refine iSup_le fun M ↦ ?_ rw [ENat.mul_iSup] refine iSup_le fun hM ↦ ?_
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|.
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_cardhave 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`.
- In Lean's SimpleGraph library, an edge is an unordered pair in `Sym2 V`. Extracting concrete endpoints requires classical choice on the existence lemma `graph_matching_num_two_mul_le_card_endpoints_of_mem_edgeSet`.
- The matching number is defined in `ℕ∞` as a supremum, so the cardinal arithmetic is performed over extended natural numbers using lemmas such as `ENat.mul_iSup` and `ENat.card_prod`.
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.
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