graph_is_maximum_matching_bot
The empty subgraph is a maximum matching of the empty graph.
Statement
theorem graph_is_maximum_matching_bot {V : Type*} : graph_is_maximum_matching (⊥ : SimpleGraph V) ⊥
- Source
- folklore
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- graph_is_maximum_matchingA subgraph M of a simple graph G is a maximum matching if M is a matching and its edge cardinality equals the matching number of G.
- graph_matching_num_botThe matching number of the empty graph (bot) is 0.
- graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
Read back from the Lean
For any type V, the empty subgraph ⊥ is a maximum matching of the empty simple graph ⊥ on V. That is, ⊥ is a matching in (⊥ : SimpleGraph V), and the extended natural cardinality of the edge set of ⊥ equals the matching number of (⊥ : SimpleGraph V).
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 unfolds the definition of a maximum matching into two conditions: that the empty subgraph is a valid matching and that its edge count equals the graph's matching number. The first condition holds vacuously because the empty subgraph has no vertices, while the second holds because both the empty subgraph's edge count and the empty graph's matching number are zero.
The empty subgraph is a maximum matching of the empty graph. automation
Unfolding the definition of a maximum matching (`graph_is_maximum_matching`), we need to verify two conditions: that the empty subgraph is a matching (`SimpleGraph.Subgraph.IsMatching`), which holds vacuously since it contains no vertices, and that its edge cardinality equals the matching number of the empty graph, which holds because both sides evaluate to 0 (using `graph_matching_num_bot`). The simplifier simplifies all terms and closes the goal.
uses
graph_is_maximum_matching,graph_matching_num_bot,SimpleGraph.Subgraph.IsMatchingsimp [graph_is_maximum_matching, graph_matching_num_bot, SimpleGraph.Subgraph.IsMatching]
graph_is_maximum_matching- A subgraph is a maximum matching if it is a matching and its edge cardinality equals the matching number of the graph.
graph_matching_num_bot- The matching number of the empty graph on any vertex type is 0.
SimpleGraph.Subgraph.IsMatching- A subgraph is a matching if every vertex in its vertex set is adjacent to exactly one vertex in the subgraph.
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 empty subgraph is a maximum matching of the empty graph. -/theorem graph_is_maximum_matching_bot {V : Type*} : graph_is_maximum_matching (⊥ : SimpleGraph V) ⊥ := by simp [graph_is_maximum_matching, graph_matching_num_bot, SimpleGraph.Subgraph.IsMatching]