# Tutte Berge formula implies Konig´s theorem

Tutte–Berge formula is for maximum size of a matching:

The theorem states that the size of a maximum matching of a graph $G = (V, E)$ equals

$$\frac{1}{2} \min_{U\subseteq V} \left(|U|-\text{odd}(G-U)+|V|\right).$$

where $odd(H)$ is the number of components in the graph H with an odd number of vertices.

König's theorem, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. The question is, can konig's theorem be derived from Tutte–Berge formula? How to apply Tutte-Berge formula to bipartite graphs? Any help would be greatly appreciated!

Let $G=(A\cup B,E)$ bipartite. If $U$ is a vertex cover of $G$ then $G-U$ has only isolated points, which are odd connected components. So $\vert U \vert +\vert V \vert -\text{odd}(G-U)=\vert U \vert +\vert V \vert -\vert V \vert+\vert U \vert=2\vert U \vert$
We will show that the quantity $\vert U \vert +\vert V \vert -\text{odd}(G-U)$ is minimized by a vertex cover. By Tutte-Berge formula this implies König's theorem.
Let $U\subseteq V$, which is not a vertex cover. Let $H$ be a connected component of $G-U$. Then $H=(A|_H,B|_H,E|_H)$ is bipartite as well. Assume w.l.o.g. that $\vert A|_H\vert\leq \vert B|_H\vert$, and let $\bar{U}=U\cup A|_H$. If $H$ is an even connected component of $G-U$ then the odd connected components of $G-\bar{U}$ are the odd connected components of $G-U$ and the points of $B|_H$. So \begin{eqnarray} \vert \bar{U} \vert -\text{odd}(G-\bar{U}) & = &\vert U\vert +\vert A|_H\vert -(\text{odd}(G-U)+\vert B|_H\vert)\\ & = & \vert U\vert -\text{odd}(G-U)+\vert A|_H\vert -\vert B|_H\vert\\ & \leq & \vert U\vert -\text{odd}(G-U) \end{eqnarray} If $H$ is an odd connected component of $G-U$, then the odd connected components of $G-\bar{U}$ are the odd connected components of $G-U$ and the points of $B|_H$ minus $H$ itself. Also $\vert A|_H\vert+1\leq \vert B|_H\vert$. So \begin{eqnarray} \vert \bar{U} \vert -\text{odd}(G-\bar{U}) & = &\vert U\vert +\vert A|_H\vert -(\text{odd}(G-U)+\vert B|_H\vert-1)\\ & = & \vert U\vert -\text{odd}(G-U)+1+\vert A|_H\vert -\vert B|_H\vert\\ & \leq & \vert U\vert -\text{odd}(G-U) \end{eqnarray} Then, if we add to $U$ the "smaller side" ($A|_H$ or $B|_H$) of every connected component of $G-U$ we construct a set $U^{*}$ such that is a vertex cover and such that $\vert U^* \vert -\text{odd}(G-U^*)\leq \vert U \vert -\text{odd}(G-U)$
Let $U$ such that minimizes $\vert U \vert +\vert V \vert -\text{odd}(G-U)$. By what we showed, we can assume $U$ is a vertex cover, in which case it is easy to see $U$ is a minimal vertex cover. By Tutte-Berge, for $M$ a matching of maximum size, $$\vert M\vert=\frac{\vert U \vert +\vert V \vert -\text{odd}(G-U)}{2}=\vert U\vert$$