AFTD Auto-Formalizing Theoretical Domains

graph_matching_num_le_vertex_cover_num

theoremverifiedformalization

In any simple graph G, the matching number is at most the vertex cover number.

Statement

theorem graph_matching_num_le_vertex_cover_num {V : Type*} (G : SimpleGraph V) : graph_matching_num G ≤ G.vertexCoverNum
Formalizes
standard textbook result (graph theory: matching number <= vertex cover number, the easy half of König's theorem)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 2

Lean source view module on GitHub

/-- Weak duality: matching number is bounded above by vertex cover number. -/theorem graph_matching_num_le_vertex_cover_num {V : Type*} (G : SimpleGraph V) : graph_matching_num G ≤ G.vertexCoverNum := by  obtain ⟨s, hs1, hs2⟩ := G.vertexCoverNum_exists  exact iSup_le fun M => iSup_le fun hM => hs1 ▸ graph_matching_encard_le_vertex_cover_encard G M s hM hs2
See it in the graphDiscuss this resultChallenge it