AFTD Auto-Formalizing Theoretical Domains

vertex_cover_num_le_two_mul_matching_num

theoremverifiedformalization

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).

  1. 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`).

    line 4

    uses exists_isMatching_isVertexCover

      obtain ⟨M, hM, hcov⟩ := exists_isMatching_isVertexCover G
  2. The 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`.

    lines 5–7

    uses iInf_le_of_le, iInf_le

      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)
  3. 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`.

    lines 8–9

    uses isMatching_verts_encard_le_two_mul

      have h2 : M.verts.encard ≤ 2 * M.edgeSet.encard :=
        isMatching_verts_encard_le_two_mul M hM
  4. The 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`.

    lines 10–12

    uses le_iSup_of_le, le_iSup

      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)
  5. 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`.

    lines 13–14

    uses mul_le_mul_right

      have h4 : 2 * M.edgeSet.encard ≤ 2 * graph_matching_num G :=
        mul_le_mul_right h3 2
  6. The 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.

    line 15

      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

/-- 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)
See it in the graphDiscuss this resultChallenge it