graph_matching_num
def
The matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
Statement
noncomputable def graph_matching_num {V : Type*} (G : SimpleGraph V) : ℕ∞
- Defined in
- standard textbook definition (graph theory: matching number)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Used by 13
- simple_graph_reconfiguration_diam_gt_matchingThe predicate on a natural number Δ asserting that there exists a finite simple graph G on a finite type V with decidable equality and…
- graph_matching_num_two_mulTwice the matching number of G equals the supremum of twice the edge cardinalities of all matchings in G.
- residual_matching_num_single_edge_exchange_iff_criticalLet G be a finite simple graph on a finite vertex type V, M a maximum matching of G, u an M-free vertex, and vw an edge of M such that uv…
- 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.
- konig_matching_vertex_cover_numKönig's theorem: in any finite bipartite simple graph G, the matching number is equal to the vertex cover number.
- graph_matching_num_le_encard_edgeSetIn any simple graph G, the matching number is at most the cardinality of the edge set.
- graph_matching_num_monoIf G and G' are simple graphs on the same vertex set with G ≤ G', then the matching number of G is at most the matching number of G'.
- op_1611_min_max_degree_le_eightThe natural number 8 satisfies simple_graph_reconfiguration_diam_gt_matching 8.
- graph_matching_num_le_vertex_cover_numIn any simple graph G, the matching number is at most the vertex cover number.
- graph_matching_num_two_mul_le_cardIn any finite simple graph G on vertex set V, twice the matching number is at most the number of vertices, 2 * graph_matching_num G ≤ |V|.
- graph_is_maximum_matching_botThe empty subgraph is a maximum matching of the empty graph.
- 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.
- graph_matching_num_botThe matching number of the empty graph (bot) is 0.
Lean source view module on GitHub
/-- The matching number of a graph, defined as the supremum of cardinalities of edge sets of matchings in G. -/ noncomputable def graph_matching_num {V : Type*} (G : SimpleGraph V) : ℕ∞ := ⨆ (M : SimpleGraph.Subgraph G) (_ : M.IsMatching), M.edgeSet.encard