Abstract The matching polyhedron theorem of Edmonds and Johnson, which gives the convex hull of capacitated perfect b‐matchings of a bidirected graph, is proved by reducing this matching problem to the ordinary perfect 1–matching problem, for which there exists a short inductive proof of the corresponding polyhedral theorem. The proof method makes it possible to deduce nestedness and discreteness properties of optimal dual solutions to the general matching problem from analogous properties of optimal dual solutions to the perfect 1–matching problem. In particular, the total dual half‐integrality of the inequality system for general matching is shown to follow from that for 1–matching. Applications considered include determining the convex hull of unions of disjoint circuits of a graph.

article Free Access Share on Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems Authors: Jack Edmonds Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, CanadaView Profile , Richard M. Karp College of Engineering, Operations Research Center, University of California, Berkeley, California College of Engineering, Operations Research Center, University of California, Berkeley, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 19Issue 2April 1972 pp 248–264https://doi.org/10.1145/321694.321699Published:01 April 1972Publication History 1,682citation6,930DownloadsMetricsTotal Citations1,682Total Downloads6,930Last 12 Months607Last 6 weeks140 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF