Finite regular bipartite graphs of positive degree have perfect matchings
ProvedOPG37364.regular_bipartite_hasPerfectMatchingbipartite-graphsgraph-theoryhall-theoremperfect-matchings
Let be a finite simple bipartite graph, and let be a positive integer. If every vertex has exactly neighbors, then has a perfect matching.
Equivalently, there is a map satisfying
Adjacency in a simple graph excludes fixed points. Connectedness is not required. This standard consequence of Hall's marriage theorem supplies the final perfect-matching step in Lemma 5, including its degree-fourteen instance.
Preamble
import Definitions.Def_opg37364_matching_cuts set_option autoImplicit false
Formal statement
namespace OPG37364
universe u
theorem regular_bipartite_hasPerfectMatching {V : Type u} [Finite V]
(G : SimpleGraph V) (d : ℕ) (hd : 0 < d)
(hreg : IsRegularOfDegree G d) (hbip : IsBipartite G) :
HasPerfectMatching G := by sorry
end OPG37364Source
The standard regular-bipartite consequence of Hall's Marriage Theorem, used in the final sentence of the proof of Lemma 5, Feghali--Lucke--Paulusma--Ries, Algorithmica 87 (2025), https://link.springer.com/article/10.1007/s00453-025-01318-8. Finite Hall infrastructure: https://github.com/leanprover-community/mathlib4/blob/0df444a360eaa60ab8c11dca51a86af692955474/Mathlib/Combinatorics/Hall/Finite.lean
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.