 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 isIts linear programming relaxation iswith the same objective function. Explicit upper bounds $x_e\le 1$ 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,\dots ,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. ChooseThen $x^{+}=x+\epsilon h$ and $x^{-}=x-\epsilon 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 $\epsilon >0$ smaller than these two slacks and smaller than every $x_e$ and $1-x_e$ along the graph path. Both $x+\epsilon h$ and $x-\epsilon h$ remain feasible: the endpoint sums can increase or decrease by $\epsilon$, 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. ThereforeThe 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.