Matchings in Arbitrary Graphs
Richard A. Brualdi · Mathematical Proceedings of the Cambridge Philosophical Society · 1971
1. Tutte(10) has given necessary and sufficient conditions in order that a finite graph have a perfect matching. A different proof was given by Gallai(4). Berge(1) (and Ore (7)) generalized Tutte's result by determining the maximum cardinality of a matching in a finite graph. In his original proof Tutte used the method of skew symmetric determinants (or pfaffians) while Gallai and Berge used the much exploited method of alternating paths. Another proof of Berge's theorem, along with an efficient algorithm for constructing a matching of maximum cardinality, was given by Edmonds (2). In another paper (12) Tutte extended his conditions for a perfect matching to locally finite graphs.