Edmonds' matching polytope theorem

From Egres Open
Jump to: navigation, search

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].


  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.