vertex_cover_num_le_two_mul_matching_num
In any finite simple graph G, the vertex cover number is at most twice the matching number: G.vertexCoverNum ≤ 2 * graph_matching_num G.
Statement
theorem vertex_cover_num_le_two_mul_matching_num {V : Type*} [Finite V] (G : SimpleGraph V) : G.vertexCoverNum ≤ 2 * graph_matching_num G
- Formalizes
- Vazirani (2001), Approximation Algorithms, Theorem 1.1
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod. - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- isMatching_verts_encard_le_two_mulFor any matching M in a graph G, the number of vertices in M is at most twice the number of edges in M.
- exists_isMatching_isVertexCoverIn any finite graph G, there exists a matching M such that M.verts is a vertex cover of G (i.e. an inclusion-maximal matching).
Read back from the Lean
For every finite type V and every simple graph G on V, the vertex cover number of G (G.vertexCoverNum) is less than or equal to 2 times the matching number of G (graph_matching_num G).
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 proof proceeds by choosing a matching M of G whose vertices form a vertex cover of G (which exists in any finite graph, for example by taking a maximal matching). Because the vertices of M form a vertex cover, the vertex cover number τ(G) is at most |V(M)|. Since M is a matching, its vertices consist of at most two endpoints per edge, so |V(M)| ≤ 2 |E(M)|. Finally, the number of edges in M is at most the matching number ν(G), yielding the chain of inequalities τ(G) ≤ |V(M)| ≤ 2 |E(M)| ≤ 2 ν(G).
There exists a matching M in G whose vertices form a vertex cover of G.
By `exists_isMatching_isVertexCover`, any finite simple graph contains a matching M whose vertex set covers all edges of G. We obtain such a matching M, along with the proofs that M is a matching (`hM`) and that its vertices cover G (`hcov`).
uses
exists_isMatching_isVertexCoverobtain ⟨M, hM, hcov⟩ := exists_isMatching_isVertexCover GThe vertex cover number of G is at most the number of vertices in M.
The vertex cover number of G is defined as the infimum of the cardinalities of all vertex covers of G. Since the vertex set of M is a vertex cover (`hcov`), this infimum is at most the cardinality of M's vertices, established by applying `iInf_le_of_le` and `iInf_le`.
uses
iInf_le_of_le,iInf_lehave h1 : G.vertexCoverNum ≤ M.verts.encard := by unfold SimpleGraph.vertexCoverNum exact iInf_le_of_le M.verts (iInf_le (fun (_ : G.IsVertexCover M.verts) => M.verts.encard) hcov)
The number of vertices in M is at most twice the number of edges in M.
Since M is a matching (`hM`), every edge has two endpoints and no two edges share an endpoint, so the number of vertices in M is at most twice its number of edges by `isMatching_verts_encard_le_two_mul`.
uses
isMatching_verts_encard_le_two_mulhave h2 : M.verts.encard ≤ 2 * M.edgeSet.encard := isMatching_verts_encard_le_two_mul M hMThe number of edges in M is at most the matching number of G.
The matching number of G is defined as the supremum of edge cardinalities over all matchings of G. Since M is a matching (`hM`), its edge cardinality is bounded above by this supremum, which is shown using `le_iSup_of_le` and `le_iSup`.
uses
le_iSup_of_le,le_iSuphave h3 : M.edgeSet.encard ≤ graph_matching_num G := by unfold graph_matching_num exact le_iSup_of_le M (le_iSup (fun (_ : M.IsMatching) => M.edgeSet.encard) hM)
Twice the number of edges in M is at most twice the matching number of G.
Multiplying the inequality |E(M)| ≤ graph_matching_num G on the left by 2 preserves the order, via `mul_le_mul_right`.
uses
mul_le_mul_righthave h4 : 2 * M.edgeSet.encard ≤ 2 * graph_matching_num G := mul_le_mul_right h3 2The vertex cover number of G is at most twice the matching number of G.
Chaining the inequalities G.vertexCoverNum ≤ |V(M)| ≤ 2 * |E(M)| ≤ 2 * graph_matching_num G together by transitivity completes the proof.
exact h1.trans (h2.trans h4)
exists_isMatching_isVertexCover- In any finite simple graph, there exists a matching whose vertex set is a vertex cover of the graph.
iInf_le_of_le- In a complete lattice, the infimum of a family is bounded above by any upper bound of a single member of the family.
iInf_le- In a complete lattice, the infimum of a family is at most any given member of the family.
isMatching_verts_encard_le_two_mul- For any matching in a simple graph, the cardinality of its vertex set is at most twice the cardinality of its edge set.
le_iSup_of_le- In a complete lattice, any lower bound of a single member of a family is bounded above by the supremum of the family.
le_iSup- In a complete lattice, any member of a family is at most the supremum of the family.
mul_le_mul_right- If b ≤ c, then multiplying on the left by a preserves the inequality: a * b ≤ a * c.
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.
/-- The vertex cover number is at most twice the matching number in any finite simple graph. -/theorem vertex_cover_num_le_two_mul_matching_num {V : Type*} [Finite V] (G : SimpleGraph V) : G.vertexCoverNum ≤ 2 * graph_matching_num G := by obtain ⟨M, hM, hcov⟩ := exists_isMatching_isVertexCover G have h1 : G.vertexCoverNum ≤ M.verts.encard := by unfold SimpleGraph.vertexCoverNum exact iInf_le_of_le M.verts (iInf_le (fun (_ : G.IsVertexCover M.verts) => M.verts.encard) hcov) have h2 : M.verts.encard ≤ 2 * M.edgeSet.encard := isMatching_verts_encard_le_two_mul M hM have h3 : M.edgeSet.encard ≤ graph_matching_num G := by unfold graph_matching_num exact le_iSup_of_le M (le_iSup (fun (_ : M.IsMatching) => M.edgeSet.encard) hM) have h4 : 2 * M.edgeSet.encard ≤ 2 * graph_matching_num G := mul_le_mul_right h3 2 exact h1.trans (h2.trans h4)