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 theoremGiven 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.

## Proof by Induction

**To Be Done**