Before revision:  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.
After revision:  The 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.