AFTD Auto-Formalizing Theoretical Domains

graph_is_maximum_matching

def

A 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.

Statement

def graph_is_maximum_matching {V : Type*} (G : SimpleGraph V) (M : G.Subgraph) : Prop
Defined in
arXiv:2610.27833, Section 1.1
Verified
21 Oct 2026
Axioms
none listed
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 2

Read back from the Lean

Given a type V, a simple graph G on V, and a subgraph M of G, graph_is_maximum_matching G M asserts that M is a matching in G (M.IsMatching) and the extended cardinality (Set.encard) of the edge set of M is equal to the matching number of G (graph_matching_num G).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A subgraph M of G is a maximum matching if M is a matching and |M| = ν(G). -/
def graph_is_maximum_matching {V : Type*} (G : SimpleGraph V) (M : G.Subgraph) : Prop := M.IsMatching ∧ M.edgeSet.encard = graph_matching_num G
See it in the graphDiscuss this resultChallenge it