# Edmonds' matching polytope theorem

Theorem (Edmonds)[1]. Let G=(V,E) be an undirected graph. The convex hull of the characteristic vectors of matchings of G is described by the linear system

$x \in {\mathbb R}^E_+$

$d_x(v) \leq 1$ for every $v \in V$

$x(E[U]) \leq (|U|-1)/2$ for every $U \subseteq V$ with $|U|$ odd.

It was shown by Cunningham and Marsh [2] that the above system is total dual integral. This result has several generalizations, for example to even factors [3].

## References

1. J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, J. of Res. the Nat. Bureau of Standards 69 B (1965), 125-130. NIST link
2. W. H. Cunningham, A. B. Marsh, A primal algorithm for optimum matching, Mathematical Programming Studies 8 (1978), 50-72, Springer link.
3. T. Király, M. Makai, On polyhedra related to even factors, Springer link, EGRES Technical Report.