**This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.**

### Abstract

A *matching* in a graph *G* is a subset *M* of the
edges of *G* such that no two share an endpoint. A matching has maximum
cardinality if its cardinality is at least as large as that of any other
matching. An *odd-set cover* *OSC* of a graph *G* is a
labeling of the nodes of *G* with integers such that every edge of
*G* is either incident to a node labeled 1 or connects two nodes
labeled with the same number *i ≥ 2*.

This article proves Edmonds theorem:

Let *M* be a matching in a graph *G* and let *OSC* be an
odd-set cover of *G*.
For any *i ≥ 0*, let `n(i)` be the number of nodes
labeled *i*. If *|M| = n(1) +
∑ _{i ≥ 2}(n(i) div 2)*,
then

*M*is a maximum cardinality matching.