exists_isMatching_isVertexCover
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
- 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
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.
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.
uses
False.elim,Finite.exists_maxclassical 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 => ?_⟩
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.
uses
Or.inl,Or.inrby_contra h have hv : v ∉ M.verts := fun hvin => h (Or.inl hvin) have hw : w ∉ M.verts := fun hwin => h (Or.inr hwin)
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.
uses
SimpleGraph.Subgraph.IsMatching.subgraphOfAdj,SimpleGraph.subgraphOfAdj_verts,Set.disjoint_insert_right,Set.disjoint_singleton_rightlet 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
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.
uses
SimpleGraph.Subgraph.verts_sup,SimpleGraph.subgraphOfAdj_verts,Set.subset_union_lefthave 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
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.
uses
Set.ncard_lt_ncardhave 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`.
- Mathlib defines `SimpleGraph.Subgraph.IsMatching M` to mean that every vertex in `M.verts` has degree exactly 1 in `M`. Consequently, the empty subgraph ⊥ has an empty vertex set and is vacuously a matching.
- Rather than choosing an inclusion-maximal matching directly, the proof chooses a matching of maximum vertex cardinality `M.verts.ncard`. In a finite graph, such a maximum matching is necessarily inclusion-maximal, so its vertices form a vertex cover.
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.
/-- 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