A perfect matching of a graph \(G=(V,E)\) is a spanning \(1\)-regular subgraph; equivalently, it is a subset \(F \subseteq E(G)\) such that degree of each vertex in \((V,F)\) is exactly one.
The study of perfect matchings has its roots in Tait's (1880) reformulation of Four Color problem.
Tutte (1947) gave the characterization of matchable graphs (that is, graphs that admit a perfect matching) whereas Edmonds (1965) characterized the perfect matching polytope (a geometric object arising from study of perfect matchings).
Minkowski-Weyl theorem states that every convex polytope is the set of solutions to a system of linear inequalities. Each perfect matching \(M\) of a matchable graph \(G\) may be considered as a \(0\)-\(1\) vector \(x \in \mathbb{R}^E\), where coordinates are indexed by edges and \(x(e) = 1\) if and only if \(e \in M\). The perfect matching polytope of a graph is the convex hull of \(0\)-\(1\) vectors of all its perfect matchings. A graph is called Birkhoff-von Neumann if its perfect matching polytope can be completely described by non-negativity and degree constraints (that is, sum at each vertex is~\(1\)).
Birkhoff (1973) and von Neumann (1954) showed that this holds for bipartite graphs, though certain non-bipartite graphs also satisfy this property. In this talk, we discuss the graph-theoretic characterization of Birkhoff-von Neumann graphs due to Balas (1981).
