1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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, \begin{equation} \vert M\vert=\frac{\vert U \vert +\vert V \vert -\text{odd}(G-U)}{2}=\vert U\vert \end{equation}

$\endgroup$
2
  • $\begingroup$ Where is the proof of equality? its tute Berges proof $\endgroup$
    – rrrto2005
    Oct 25 '15 at 1:30
  • $\begingroup$ @rrrto2005 Sorry if the proof I linked before was not clear, or if it didn't answer properly your question. I have posted a different proof this time. This time, it is a proof of the equality. $\endgroup$
    – Nate River
    Oct 25 '15 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.