A Simple Criterion for a Graph to have a Perfect Matching

Abstract

The first characterization of graphs having a 1-factor (perfect matching) was provided by W.T. Tutte in what has become a classic result in graph theory with applications to operations research:

Graph G has a perfect matching if and only if for all S⊂V, the number of odd components of G – S is not greater than | S |. Our purpose is to present a simple constructive criterion using the following concept: A factor F of G has the isolate-joining alternating path property if for every isolated point V of F there is another isolated point W of F such that there exists an alternating path from V to W. Then our theorem slates that G has a 1-factor if and only if every factor of G whose components are just K ₁ or K ₂ has this alternating path property.