# Konig's theorem

| Tags Algorithm

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

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.

To Be Done