isMatching_verts_encard_le_two_mul
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
- vertex_cover_num_le_two_mul_matching_numIn any finite simple graph G, the vertex cover number is at most twice the matching number: G.vertexCoverNum ≤ 2 * graph_matching_num G.
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.
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.
uses
Quot.out_eqhave h := x.1.2 have hq := Quot.out_eq x.1.val rw [← hq] at h exact M.mem_edgeSet.mp h
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.
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⟩
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.
uses
Quot.out_eq,Sym2.eq_iffhave 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⟩
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.
uses
Subtype.ext· use (e, 0) exact Subtype.ext h1 · use (e, 1) exact Subtype.ext h2
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.
uses
isMatching_verts_encard_le_two_mul_endpoint_surjective,ENat.card_le_card_of_injective,Function.injective_surjInvhave 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)
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.
uses
ENat.card_prod,mul_comm,ENat.card_coe_set_eqrw [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.
- In Lean's SimpleGraph library, undirected edges are defined as unordered pairs via the quotient type `Sym2 V`. Extracting the endpoints of an edge requires choosing a representative ordered pair using `Quot.out` and reasoning about the equivalence relation `Sym2.Rel`.
- The cardinalities are stated using extended natural numbers (`ENat.card` and `Set.encard`), so the result holds for both finite and infinite graphs.
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.
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