Theorem (P), p. 126 — the vertices of the polyhedron C are exactly the matching vectors of G

Let $G$ be a finite graph with node set $V$ and edge set $E$. Let $C\subseteq\mathbb R^E$ be the polyhedron of vectors $x=(x_e)_{e\in E}$ satisfying

1. $x_e\ge 0$ for every edge $e$;
2. $\sum_{e\text{ meets }v}x_e\le 1$ for every node $v$;
3. $\sum_{e\text{ has both ends in }S}x_e\le r$ for every set $S$ of $2r+1$ nodes, $r$ a strictly positive integer;

and let $P$ be the set of matching vectors: the vectors with all components $0$ or $1$ that satisfy (2), i.e. the incidence vectors of matchings of $G$.

Theorem (P). $P$ is the set of vertices (extreme points) of $C$:

Consequently, for any real edge weights $c$, the maximum weight of a matching equals the maximum of the linear form $\sum_e c_e x_e$ over $C$: maximum-weight matching is a linear program over a polyhedron described by explicit inequalities. This is the first polyhedral description of the matching polytope of a general (non-bipartite) graph.

Formalization Note The graph is given by a finite node type $V$, a finite edge type $E$ and, for each edge, the unordered pair of its ends (no loops). Parallel edges are allowed, which covers the contracted graphs of Theorem (M); a simple graph is the special case of an injective end map. Vectors $x$ have one real coordinate per edge.