In the mathematical area of graph theory, Konig's theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs.
Konig's theorem
Given a bipartite graph $$$G=(V,E)$$$: min |C| = max |M|
Proof by Narrow
We can break the proof into two steps. Firstly, we can prove that |C| $$$ \ge $$$ |M|, and secondly, we prove that min|C| $$$ \le $$$ max|M|, then Konig's theorem gets proved.
First Step
It is very easy to prove that |C| $$$ \ge $$$ |M| for any vertex cover an matching in the same bipartite graph. Because each edge of the matching must be covered by the vertex cover, so at least one vertex of each edge must in the set of vertex cover, thus we proved that |C| $$$ \ge $$$ |M| at any circumstance.
Second Step
In this step, we just need to prove that min|C| $$$ \le $$$ |M| for some matching M. Given a minimal vertex cover C, if we can extend it into a matching, then we gets proved.
To Be Done
Proof by Duality
If we convert maximum matching problem and minimum vertex cover problem into Linear Programming problems, then we can prove Konig's theorem elegantly by using duality.
Given a bipartite graph $$$ G=(V,E) $$$, the maximum matching can be defined as:
$$$ max \sum_{e \in E} x_e $$$
s.t.
$$$ \sum_{e \in \delta(v)} x_e \le 1 $$$
$$$ x_e \ge 0 $$$
The minimum vertex cover can be defined as:
$$$ min \sum_{v \in G} y_v $$$
s.t.
$$$ \sum_{(u,v) \in E} y_u + y_v \ge 1 $$$
$$$ y_v \ge 0 $$$
We can easily rewrite the above two linear programming problems into primary-dual format. First, we can define a matrix A, where A is a |V| $$$ \times $$$ |E| matrix, $$$ A_{ij} = 1 $$$ if verteix i is an end point of edge j, otherwise, $$$ A_{ij} = 0 $$$. Then the maximum matching can be defined as:
$$$ max 1^T X $$$
s.t.
$$$ AX \le 1 $$$
$$$ X \ge 0 $$$
And the minimum vertex cover can be defined as:
$$$ min Y 1^T $$$
s.t.
$$$ Y^T A \ge 1 $$$
$$$ Y \ge 0 $$$
Due to the primary-dual property of linear programming, we can certainly say that Konig's theorem gets proved.