# Edmonds' matching polytope theorem

From Egres Open

**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

[math]x \in {\mathbb R}^E_+[/math]

[math]d_x(v) \leq 1[/math] for every [math]v \in V[/math]

[math]x(E[U]) \leq (|U|-1)/2[/math] for every [math]U \subseteq V[/math] with [math]|U|[/math] 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

- ↑ 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 - ↑ W. H. Cunningham, A. B. Marsh,
*A primal algorithm for optimum matching*, Mathematical Programming Studies 8 (1978), 50-72, Springer link. - ↑ T. Király, M. Makai,
*On polyhedra related to even factors*, Springer link, EGRES Technical Report.