graph_matching_num_bot
theoremverifiedformalization
The matching number of the empty graph (bot) is 0.
Statement
theorem graph_matching_num_bot {V : Type*} : graph_matching_num (⊥ : SimpleGraph V) = 0
- Formalizes
- standard textbook result (graph theory: the empty graph has matching number 0)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
- Used by 1
- graph_is_maximum_matching_botThe empty subgraph is a maximum matching of the empty graph.
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 graph has matching number 0. -/theorem graph_matching_num_bot {V : Type*} : graph_matching_num (⊥ : SimpleGraph V) = 0 := by unfold graph_matching_num apply le_antisymm · refine iSup_le fun M => iSup_le fun _ => ?_ have h : M.edgeSet = ∅ := Set.subset_empty_iff.mp (SimpleGraph.edgeSet_bot ▸ M.edgeSet_subset) rw [h, Set.encard_empty] · exact zero_le