An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs

We prove that a fractional perfect matching in a non-bipartite graph can be written, in polynomial time, as a convex combination of perfect matchings. This extends the Birkhoff-von Neumann Theorem from bipartite to non-bipartite graphs. The greedy algorithm of Birkhoff and von Neumann, which starts with the given fractional perfect matching and successively "removes" from it perfect matchings, with appropriate multipliers, fails in non-bipartite graphs -- removing perfect matchings arbitrarily can lead to a graph that is non-empty but has no perfect matchings. Using odd cuts appropriately saves the day.