linguistic:translation
Proof using linear programming duality

To explain this proof, we first have to extend the notion of a matching to that of a fractional matching - an assignment of a weight in to each edge, such that the sum of weights near each vertex is at most 1 (an integral matching is a special case of a fractional matching in which the weights are in {0,1}). Similarly we define a fractional vertex-cover - an assignment of a non-negative weight to each vertex, such that the sum of weights in each edge is at least 1 (an integral vertex-cover is a special case of a fractional vertex-cover in which the weights are in {0,1}).

The maximum fractional matching size in a graph G = (V, E) {\displaystyle G=(V,E)} is the solution of the following linear program:

Maximize 1 · x

Subject to: x ≥ 0

__________ A · x ≤ 1.

where x is a vector of size | E | in which each element represents the weight of an edge in the fractional matching. 1 is a vector of | E | ones, so the first line indicates the size of the matching. 0 is a vector of | E | zeros, so the second line indicates the constraint that the weights are non-negative. 1 is a vector of | V | ones and A is the incidence matrix of G, so the third line indicates the constraint that the sum of weights near each vertex is at most 1.Similarly, the minimum fractional vertex-cover size in G = (V, E) {\displaystyle G=(V,E)} is the solution of the following LP:

Minimize 1 · y

Subject to: y ≥ 0

__________ A · y ≥ 1.

where y is a vector of size |V| in which each element represents the weight of a vertex in the fractional cover. Here, the first line is the size of the cover, the second line represents the non-negativity of the weights, and the third line represents the requirement that the sum of weights near each edge must be at least 1.Now, the minimum fractional cover LP is exactly the dual linear program of the maximum fractional matching LP. Therefore, by the LP duality theorem, both programs have the same solution. This fact is true not only in bipartite graphs but in arbitrary graphs:

In any graph, the largest size of a fractional matching equals the smallest size of a fractional vertex cover.

What makes bipartite graphs special is that, in bipartite graphs, both these linear programs have optimal solutions in which all variable values are integers. This follows from the fact that in the fractional matching polytope of a bipartite graph, all extreme points have only integer coordinates, and the same is true for the fractional vertex-cover polytope. Therefore the above theorem implies:

In any bipartite graph, the largest size of a matching equals the smallest size of a vertex cover.