Edmonds (1965): maximum matching and a polyhedron

../

blossom_contraction: Checks all weighted invariants, including an exposed minimum-weight base.

capacity_extensions: States the two capacity polyhedra without attributing their deferred proofs.

complexity_scope: Separates proved finite real-weight termination from the source's conceptual cost.

definitions: Fixes finite graph, empty-case, real-weight and dual conventions.

dual_adjustment: Lists every limiting event and proves feasibility, tightness and dual descent.

dual_certificate: Proves compatible minimum-base lifting, dual feasibility and the exact gap.

dual_sparsity: Proves the basic support bound and distinguishes arbitrary constructed certificates.

external_inputs: Identifies the Paths lemmas, finite compactness and contextual LP assertions.

finite_termination: Supplies the old-history argument and the positive-exposure progress measure.

inner_expansion: Checks tight-edge inheritance and the even-arc replacement at zero slack.

path_updates: Separates ordinary augmentation from moving exposure to a zero-weight node.

specified_optimum: Repairs zero-weight ties and proves the fixed-type compactness argument.

theorem_m: Retains all eleven source conditions and proves both directions.

theorem_p: Proves arbitrary-real-weight integrality and the exact convex-hull description.

weighted_algorithm: Assembles a finite real-weight search with a matching and an equality certificate.

weighted_hierarchy: Expands the source's nested contraction data and commutation argument.

---

Jack Edmonds, Maximum Matching and a Polyhedron With 0,1-Vertices, Journal of Research of the National Bureau of Standards—B: Mathematics and Mathematical Physics 69B, nos. 1 and 2 (January–June 1965), 125–130. DOI: 10.6028/jres.069B.013.

The copy read for this card is the six-page published original, the NIST research-library archival scan, acquired from its public Internet Archive record. The exact identity and publication metadata are recorded in source_record.json. The first page prints “December 1, 1964” without a label identifying it as a received date. The journal issue is January–June 1965. Only this mathematical version was read; no author-manuscript or later-version equivalence is asserted. No notice is printed in the file, and the DOI resolves straight to the PDF with no landing page; the Internet Archive record it was acquired from (https://archive.org/details/jresv69Bn1-2p125) states "The Journal of Research of the National Institute of Standards and Technology is a publication of the U.S. Government. The papers are in the public domain and are not subject to copyright in the United States."; the library's license vocabulary has no public-domain term, so the term is recorded as unstated.

Results and proof coverage

Theorem P says that nonnegativity, vertex constraints and odd-set constraints describe the convex hull of all matching indicators. Its scope is every real edge objective, including zero and negative weights. It is the stronger result deferred by Paths, Trees and Flowers, Section 5.5, whose cardinality LP proof is already separate.

The complete rewritten route retains the source's weighted structure: hierarchies and reordering, conversion to a dual certificate, tight contraction, two path updates, cap-triggered inner expansion, and the exact weight adjustment. The finite-history argument establishes termination for real weights, and the assembled algorithm produces equality of matching and dual objectives.

Theorem M retains all eleven structural conditions. Its stronger conclusion for any specified optimum uses the separate perturbation and compactness proof. The source's zero-weight uniqueness shortcut is repaired there by a signed perturbation, and completed-certificate equality supplies a uniform bound before taking a fixed-type limit.

The dual support page proves the extreme-point bound and gives an explicit example showing why it is not automatic for every constructed certificate. The finite bounded-polytope step is proved in Theorem P without repeating the source's broader unsupported vertex-optimizer sentence for polyhedra with lineality. These qualifications and expansions are supplied by the compilation; they are not described as an author-issued erratum.

Boundaries and connections

The external-input page gives exact original Paths interfaces and finite-dimensional foundations. General strong LP duality is stated but is not needed to close the direct equality-certificate proof.

Section 8's capacity extensions are precise announced statements without their deferred proofs. The operation-count discussion remains at source scope: no checked implementation, bit-complexity proof or formal build is claimed.

Bears on. None of the problem pages directly.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.