= Solution
Let $G=(L\cup R,E)$ be the given <bipartite graph>. A <matching in a graph> selects <edges> with no shared endpoint. For each <edge> $e$, introduce an indicator $x_e$ for selection. The <integer program> for a <maximum cardinality matching> is
$$
\boxed{
\begin{aligned}
\max\quad&\sum_{e\in E}x_e\\
\text{subject to}\quad&\sum_{e\ni v}x_e\leq1&& (v\in L\cup R),\\
&x_e\in\{0,1\}&& (e\in E).
\end{aligned}}
$$
Its <linear programming relaxation> is
$$
P=\left\{x\in\mathbb R^E:x_e\geq0\ (e\in E),\quad\sum_{e\ni v}x_e\leq1\ (v\in L\cup R)\right\},
$$
with the same <objective function>. Explicit upper bounds $x_e\leq1$ may be included, but they already follow from a constraint at either endpoint.
We prove that every <extreme point> of $P$ is integral by showing that any <feasible point> with a fractional coordinate admits a two-sided perturbation. Given such an $x$, form the <fractional support graph> $H$ with exactly those <edges> for which $0<x_e<1$. This is a nonempty <bipartite graph>. A <vertex> incident to one of these <edges> cannot also meet an <edge> with value $1$, because its incident sum would exceed $1$.
First suppose $H$ contains a <graph cycle>. Choose a simple one, $e_1,\ldots,e_q$. Its length $q$ is even since $H$ is a <bipartite graph>. Define a nonzero <vector> $h$ by alternating $+1,-1$ along the <graph cycle> and putting $0$ on other <edges>. At each <vertex> on the <graph cycle>, the two changed coordinates have opposite signs, so its incident sum is unchanged. Choose
$$
0<\varepsilon<\min_{e\text{ on the cycle}}\{x_e,1-x_e\}.
$$
Then $x^+=x+\varepsilon h$ and $x^-=x-\varepsilon h$ are distinct <feasible points>: no coordinate leaves $[0,1]$ and all incident sums are unchanged. Since $x=(x^++x^-)/2$, it is not an <extreme point>.
Otherwise $H$ is a <forest>. Choose a <connected component of a graph> containing an <edge>, and a simple <graph path> in it between two <tree leaves>. Alternate $+1,-1$ along the <graph path> to define $h$. Every internal <vertex> of the <graph path> still has unchanged incident sum, including any additional <edges> branching from it. At either endpoint, exactly one incident <edge> has fractional value; all other incident coordinates are $0$, since a coordinate $1$ is impossible there. Thus each endpoint has strictly positive slack $1-\sum_{e\ni v}x_e$ in its degree constraint. Choose $\varepsilon>0$ smaller than these two slacks and smaller than every $x_e$ and $1-x_e$ along the <graph path>. Both $x+\varepsilon h$ and $x-\varepsilon h$ remain feasible: the endpoint sums can increase or decrease by $\varepsilon$, and the internal sums do not change. Again $x$ is the midpoint of distinct <feasible points>, contradicting extremality.
Both cases exclude fractional coordinates at an <extreme point>. Therefore
$$
\boxed{\text{every extreme point of }P\text{ has }x_e\in\{0,1\}\text{ and represents a matching}.}
$$
The nonempty bounded <linear polyhedron> $P$ has an optimal <extreme point> for the stated <linear function>, so the relaxation yields a <maximum cardinality matching>. This is stronger than the existence of one integral optimum: it proves integrality of every <extreme point>. It does not claim that every optimal <feasible point> is integral; convex mixtures of distinct optimal <matchings in a graph> can be fractional.
Back to article page
