# Using LP to prove the max matching - min cover theorem

Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following proof, based on primal-dual linear program, is valid. This is mainly an exercise in understanding this primal-dual concept.

Step 1: define an LP for the maximum matching. For every edge $$(u,v)\in E$$, define a variable $$z_{uv}$$ whose value is 1 if the edge is in the matching. The LP is:

\begin{align} \text{maximize} && \sum_{(u,v)\in E} z_{uv} && \\ \text{subject to} && \sum_{v\in Y} z_{uv} \leq 1 && \forall u\in X \\ && \sum_{u\in X} z_{uv} \leq 1 && \forall v\in Y \\ && z_{uv}\geq 0 && \forall (u,v)\in E \end{align}

Step 2. Create the dual LP using the recipe:

• Each primal constraint becomes a dual variable - so there is a variable $$x_u$$ for each $$u\in X$$ and a variable $$y_v$$ for each $$v\in Y$$.
• The sign of each dual variable is opposite to the sign of its primal constraint - so $$x_u\geq 0, y_v\geq 0$$.
• The dual objective is minimization, where the coefficient of each dual variable is the number on the right-hand side of its primal constraint - in this case it is always 1. So the objective is "minimize $$\sum x_u + \sum y_v$$".
• Each primal variable becomes a dual constraint. The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. In this case, the coefficient of the dual variable of a node $$i$$, in the dual constraint of the edge $$(j,k)$$, should be 1 iff $$i=j$$ or $$i=k$$.
• The sign of each dual constraint is the sign of its primal variable.
• All in all, the dual LP is:

\begin{align} \text{minimize} && \sum_{u\in X} x_u + \sum_{v\in Y}y_v && \\ \text{subject to} && x_u + y_v \geq 1 && \forall (u,v)\in E \\ && x_{u}\geq 0, y_v \geq 0 && \forall u\in X, v\in Y \end{align}

The dual LP finds a minimum vertex cover - it minimizes the number of vertices under the constraint that for each edge, at least one of its endpoints is in the cover.

My question is: is this proof valid?

The main thing I am not sure at is that the LP allows fractional variables, while the original problems are integral. What argument should be added to handle this issue?