Edmonds (1965): Paths, Trees, and Flowers

../

cardinality_lp: Derives exact unweighted linear-programming relaxation from the odd-set cover without assuming the stronger weighted theorem.

complexity_scope: Records the original fourth-power time and squared-memory discussion without claiming a checked implementation.

contraction_structure: Makes the original-vertex blocks, remembered edge identities and permissible expansion order explicit.

corollary_5_9: Preserves the refined dual cover and derives the bipartite matching-cover theorem locally.

corollary_6_7: Describes the canonical preferred cover while distinguishing it from uniqueness of all minimum covers.

definitions: Fixes the finite multigraph, matching, planted-tree and remembered-contraction conventions.

edge_cover: Expands the finite mixed-cover conversion and its necessary no-isolated-vertices hypothesis.

external_inputs: Separates contextual linear-programming inputs and the deferred weighted and alternative-algorithm papers from the complete local chain.

forest_algorithm: Expands the source's alternative search growing all exposed-root trees together.

forest_reduction: Expands the forest counting argument and its odd-block form needed for the Section 6 deletion proof.

lemma_3_5: Decomposes two matchings into alternating paths and even circuits.

lemma_4_13: Shows that blossom contraction preserves plantedness and the inner-outer labels outside the blossom.

lemma_4_14: Proves the odd-circuit lift, its nested form and arbitrary prescribed exposure in a complete expansion.

lemma_4_15: Proves the stem-based optimality converse and its disjoint-subgraph extension.

lemma_4_17: Proves the matching-size decomposition across a Hungarian tree.

lemma_4_2: Proves the outer-inner count and the unique matching omitting each specified outer vertex.

lemma_4_3: Proves deterministic backward tracing in a planted tree and the resulting augmenting path.

lemma_4_5: Shows how an outer-outer edge determines a blossom and its stem.

lemma_4_7: Gives the finite branching rule leading to augmentation, a blossom or a Hungarian tree.

lemma_5_7: Supplies the perfect and near-perfect base covers, including small orders and the odd-circuit refinement.

lemma_7_2: Proves the even-arc replacement that restores a planted tree when a retained blossom becomes inner.

matching_decomposition: Extracts the precise odd-component and neighbor-matching consequences used by Edmonds–Fulkerson.

maximum_matching_algorithm: Assembles blossom search, lifting and Hungarian-tree removal into a finite constructive algorithm.

refinement_7_3: Preserves the separate refinement that retains contractions through augmentations and expands inner pseudovertices only when necessary.

theorem_3_7: Reconstructs the paper's short proof that a matching is maximum exactly when no augmenting path exists.

theorem_4_12: Combines the two distinct contraction directions under the flower hypothesis.

theorem_5_6: Reconstructs the odd-set capacity minimum by induction through Hungarian trees and blossom expansions.

theorem_6_2: Proves the intrinsic outer and inner sets and the contraction of their components, including the complete forest deletion argument.

---

Jack Edmonds, Paths, Trees, and Flowers, Canadian Journal of Mathematics 17 (1965), 449–467, DOI 10.4153/CJM-1965-045-4. The copy read for this card is the published PDF from Cambridge. Its exact identity and version details are in the source record. That copy prints only "Published online by Cambridge University Press"; the publisher's page for DOI 10.4153/CJM-1965-045-4 (read 2026-10-02) shows "Copyright © Canadian Mathematical Society 1965" and names no license, every other right reserved.

The 19 physical pages are the original printed pp. 449–467. The first page gives receipt on 22 November 1963. The publisher's 20 November 2018 online date and later PDF metadata concern digitization, not a revised theorem version. Only this published version was read; no author-manuscript equivalence is asserted. The publisher and Crossref do not supply an issue number, so the No. 3 in the later Edmonds–Fulkerson citation is not independently promoted here.

Matching search and contractions

The source works with finite loopless graphs, allowing distinct parallel edges. Its augmenting-path criterion follows from symmetric differences. The edge-cover comparison records its separate mixed-cover conversion.

The proof chain develops alternating-tree matchings, stems and augmentation, flower extraction, and exhaustive tree search. It keeps nested edge identities, planted-tree contraction, matching lifts and the stem-based optimality converse explicit. These yield blossom contraction equivalence and the complete maximum-matching algorithm.

The Hungarian-tree reduction, collective odd-block reduction and simultaneous forest algorithm expand the source's short forest analogy. The inner-pseudovertex expansion and deferred-expansion rule retain its distinct later refinement.

Duality and intrinsic structure

The odd-set matching duality uses complete refined base covers, including empty and tiny graphs. It implies the odd-circuit refinement and bipartite König theorem and the exact cardinality LP relaxation.

Theorem 6.2 identifies the vertices exposed by some maximum matching and their neighbors, and proves that the final contraction has precisely their connected components as blocks. Its two deletion cases are justified by explicit collective-forest bounds. The odd-component interface is the separate source input used in Edmonds–Fulkerson's matching-to-transversal argument. The preferred minimum cover is canonical, without asserting that every minimum cover is unique.

Precision and scope

The printed Section 5.5 says the vertex sum is “less than one”; the required weak inequality is used and explained on the cardinality page. Section 5.7's generic base-cover recipes require separate orders zero, one and two. The refined base proof also ensures an odd circuit in every nonsingleton cover member, rather than assuming that for an arbitrary perfect-case split. These are compilation-supplied clarifications, not author-issued errata.

All local proof chains above are reconstructed. The external-input page separates the full weighted matching-polytope assertion and the Witzgall–Zahn algorithm, whose proofs are not in this paper. The original conceptual time and memory discussion is not a checked implementation or an input-complexity theorem for unbounded edge multiplicity.

No numbered Erdős problem implication is added without a direct source relationship. No infinite matching theorem, current algorithmic bound, formal build or fresh mathematical status claim is made.

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