AFTD Auto-Formalizing Theoretical Domains

exists_isMatching_isVertexCover

theoremverified

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

Statement

theorem exists_isMatching_isVertexCover {V : Type*} [Finite V] (G : SimpleGraph V) :
    ∃ M : G.Subgraph, M.IsMatching ∧ G.IsVertexCover M.verts
Source
step towards vertex_cover_num_le_two_mul_matching_num
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by choosing a matching M of maximum vertex cardinality, which exists because the set of matchings in a finite graph is finite and nonempty (the empty subgraph is a matching). If M.verts were not a vertex cover, there would be an edge v ∼ w with neither endpoint in M.verts. Adding this edge to M would produce a valid matching M' with strictly more vertices, contradicting the maximality of M.

  1. There exists a matching M maximizing the number of vertices, and it suffices to show that its vertex set covers every edge.

    The empty subgraph ⊥ is vacuously a matching because it has no vertices (using `False.elim`). Since the vertex set V is finite, the collection of all matchings in G is finite and nonempty. By `Finite.exists_max`, there exists a matching M maximizing `M.verts.ncard`. We witness the existential goal with M, leaving the goal of showing that for any edge v ∼ w in G, at least one endpoint belongs to M.verts.

    lines 4–9

    uses False.elim, Finite.exists_max

      classical
      have hbot : (⊥ : G.Subgraph).IsMatching := fun v hv => False.elim (by simp at hv)
      obtain ⟨⟨M, hM⟩, hmax⟩ :=
        @Finite.exists_max { M : G.Subgraph // M.IsMatching } ℕ _ ⟨⟨⊥, hbot⟩⟩ _
          (fun M => M.val.verts.ncard)
      refine ⟨M, hM, fun v w hvw => ?_⟩
  2. Assuming for contradiction that the edge {v, w} is uncovered, neither v nor w belongs to M.verts.

    We assume for contradiction (`by_contra`) that neither endpoint is in M.verts, i.e., ¬(v ∈ M.verts ∨ w ∈ M.verts). From this, v ∉ M.verts and w ∉ M.verts, since if either belonged to M.verts, `Or.inl` or `Or.inr` would yield the disjunction.

    lines 10–12

    uses Or.inl, Or.inr

      by_contra h
      have hv : v ∉ M.verts := fun hvin => h (Or.inl hvin)
      have hw : w ∉ M.verts := fun hwin => h (Or.inr hwin)
  3. The augmented subgraph M' obtained by adding the edge {v, w} to M is also a matching.

    Define M' = M ⊔ G.subgraphOfAdj(v ∼ w). The single edge {v, w} is itself a matching by `SimpleGraph.Subgraph.IsMatching.subgraphOfAdj`, with vertex set {v, w} by `SimpleGraph.subgraphOfAdj_verts`. For any matching, its support equals its vertex set. Since neither v nor w is in M.verts, M is disjoint from {v, w} by `Set.disjoint_insert_right` and `Set.disjoint_singleton_right`. Because their supports are disjoint, the union of the two matchings is again a matching.

    lines 13–19

    uses SimpleGraph.Subgraph.IsMatching.subgraphOfAdj, SimpleGraph.subgraphOfAdj_verts, Set.disjoint_insert_right, Set.disjoint_singleton_right

      let M' : G.Subgraph := M ⊔ G.subgraphOfAdj hvw
      have hd : Disjoint M.support (G.subgraphOfAdj hvw).support := by
        rw [hM.support_eq_verts, (SimpleGraph.Subgraph.IsMatching.subgraphOfAdj hvw).support_eq_verts,
          SimpleGraph.subgraphOfAdj_verts]
        rw [Set.disjoint_insert_right, Set.disjoint_singleton_right]
        exact ⟨hv, hw⟩
      have hM' : M'.IsMatching := hM.sup (SimpleGraph.Subgraph.IsMatching.subgraphOfAdj hvw) hd
  4. The vertex set of M is strictly contained in that of M', while maximality requires |M'.verts| ≤ |M.verts|.

    By the maximality of M, |M'.verts| ≤ |M.verts|. The vertex set of M' is M.verts ∪ {v, w} by `SimpleGraph.Subgraph.verts_sup` and `SimpleGraph.subgraphOfAdj_verts`. Thus M.verts ⊆ M'.verts via `Set.subset_union_left`. Furthermore, this inclusion is strict: if M'.verts ⊆ M.verts, then v ∈ M'.verts would imply v ∈ M.verts, contradicting v ∉ M.verts.

    lines 20–31

    uses SimpleGraph.Subgraph.verts_sup, SimpleGraph.subgraphOfAdj_verts, Set.subset_union_left

      have hle := hmax ⟨M', hM'⟩
      dsimp at hle
      have hverts : M'.verts = M.verts ∪ {v, w} := by
        change (M ⊔ G.subgraphOfAdj hvw).verts = _
        rw [SimpleGraph.Subgraph.verts_sup, SimpleGraph.subgraphOfAdj_verts]
      have hss : M.verts ⊂ M'.verts := by
        rw [hverts]
        refine ⟨Set.subset_union_left, ?_⟩
        intro heq
        have hvin : v ∈ M.verts ∪ {v, w} := by simp
        have : v ∈ M.verts := heq hvin
        contradiction
  5. The strict inclusion implies |M.verts| < |M'.verts|, contradicting |M'.verts| ≤ |M.verts|.

    By `Set.ncard_lt_ncard`, strict inclusion between finite sets gives |M.verts| < |M'.verts|. The `omega` tactic detects the contradiction between |M.verts| < |M'.verts| and |M'.verts| ≤ |M.verts| by linear integer arithmetic.

    lines 32–33

    uses Set.ncard_lt_ncard

      have hlt : M.verts.ncard < M'.verts.ncard := Set.ncard_lt_ncard hss
      omega
False.elim
From a contradiction (`False`), any statement follows.
Finite.exists_max
Any function from a finite, nonempty type to a linearly ordered type attains a maximum value.
Or.inl
From a proof of `a`, deduces the disjunction `a ∨ b`.
Or.inr
From a proof of `b`, deduces the disjunction `a ∨ b`.
SimpleGraph.Subgraph.IsMatching.subgraphOfAdj
For an edge `v ∼ w` in a graph, the subgraph induced by this single edge is a matching.
SimpleGraph.subgraphOfAdj_verts
The vertex set of the single-edge subgraph induced by `v ∼ w` is `{v, w}`.
Set.disjoint_insert_right
A set `s` is disjoint from `insert a t` if and only if `a ∉ s` and `s` is disjoint from `t`.
Set.disjoint_singleton_right
A set `s` is disjoint from the singleton `{a}` if and only if `a ∉ s`.
SimpleGraph.Subgraph.verts_sup
The vertex set of the union (supremum) of two subgraphs is the union of their vertex sets.
Set.subset_union_left
A set `s` is a subset of `s ∪ t`.
Set.ncard_lt_ncard
If `s ⊂ t` and `t` is finite, then the cardinality of `s` is strictly less than the cardinality of `t`.

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

/-- In any finite simple graph G, there exists a matching M whose vertex set M.verts is a vertex cover of G. -/theorem exists_isMatching_isVertexCover {V : Type*} [Finite V] (G : SimpleGraph V) :    ∃ M : G.Subgraph, M.IsMatching ∧ G.IsVertexCover M.verts := by  classical  have hbot : (⊥ : G.Subgraph).IsMatching := fun v hv => False.elim (by simp at hv)  obtain ⟨⟨M, hM⟩, hmax⟩ :=    @Finite.exists_max { M : G.Subgraph // M.IsMatching } ℕ _ ⟨⟨⊥, hbot⟩⟩ _      (fun M => M.val.verts.ncard)  refine ⟨M, hM, fun v w hvw => ?_⟩  by_contra h  have hv : v ∉ M.verts := fun hvin => h (Or.inl hvin)  have hw : w ∉ M.verts := fun hwin => h (Or.inr hwin)  let M' : G.Subgraph := M ⊔ G.subgraphOfAdj hvw  have hd : Disjoint M.support (G.subgraphOfAdj hvw).support := by    rw [hM.support_eq_verts, (SimpleGraph.Subgraph.IsMatching.subgraphOfAdj hvw).support_eq_verts,      SimpleGraph.subgraphOfAdj_verts]    rw [Set.disjoint_insert_right, Set.disjoint_singleton_right]    exact ⟨hv, hw⟩  have hM' : M'.IsMatching := hM.sup (SimpleGraph.Subgraph.IsMatching.subgraphOfAdj hvw) hd  have hle := hmax ⟨M', hM'⟩  dsimp at hle  have hverts : M'.verts = M.verts ∪ {v, w} := by    change (M ⊔ G.subgraphOfAdj hvw).verts = _    rw [SimpleGraph.Subgraph.verts_sup, SimpleGraph.subgraphOfAdj_verts]  have hss : M.verts ⊂ M'.verts := by    rw [hverts]    refine ⟨Set.subset_union_left, ?_⟩    intro heq    have hvin : v ∈ M.verts ∪ {v, w} := by simp    have : v ∈ M.verts := heq hvin    contradiction  have hlt : M.verts.ncard < M'.verts.ncard := Set.ncard_lt_ncard hss  omega
See it in the graphDiscuss this resultChallenge it