Let $G=(V,E)$ be a graph. $H\subseteq V$ is called a vertex cover of $G$ iff $(u,v)\in E\Rightarrow u\in H\vee v\in H$. Now let's assume $G$ is bipartite, i.e. $V=V_1 \cup V_2$ and $E\subseteq V_1\times V_2$. Then König's theorem states, that the cardinality of a maximum matching in $G$ equals the minimum size of any vertex cover of $G$.
I'm asked to proof the theorem in the following steps:
- Transform the given graph into a flow network $N:=(V',E',s,t,c)$ such that any flow of value $x$ in $N$ corresponds to a matching of cardinality $x$ in $G$ and any matching of cardinality $x$ in $G$ defines a flow of value $x$ in $N$.
- Show that any vertex cover $H$ of $G$ defines a cut of capacity $H$ in $N$
- Show that any cut of capacity $k$ in $N$ defines a vertex cover of size $k$ in $G$
(1) I've set $V'=V\cup\left\{s,t\right\}$, $E'=E\cup \left\{(s,u):u\in V_1\right\}\cup\left\{(v,t):v\in V_2\right\}$ and $c(u,v)\equiv 1$ for all $(u,v)\in E'$. Then I've proved the statement.
(2) Now I would like to proof (2) as well, but I don't think it's a correct statement. Please consider $V_1=\left\{u\right\}$ and $V_2=\left\{v\right\}$. Then $G$ is a valid bipartite graph and $H=\left\{u,v\right\}$ is a vertex cover in $G$. But, any cut of $N$ has a capacity of $1\ne 2=|H|$.
Am I missing something?
EDIT: Please consider the following example
Let $V_1=\left\{A,B,C,D\right\}$ and $V_2=\left\{E,F,G,H\right\}$. The red line illustrates a cut with capacity $4$ (visualized by the orange edges each of capacity $1$). If the bold black edge from $G$ to $B$ is not present, the green nodes are a vertex cover set with cardinality $4$. The edge $(G,B)$ doesn't contribute to the capacity of any cut, because its capacity is $0$. So, how do you build a vertex cover set formally if (G,B) is present?
Best Answer
Instead of constructing $V^\prime$ so that the edges $(u, v) \in E$ have capacity $1$, let such $(u,v)$ have infinite capacity and the edges $(s,u)$ and $(v,t)$ have capacity $1$.
Then an integral flow (and there must be a maximum flow which is integral) can send at most one unit of flow through each $u\in V_1$ and $v \in V_2$, and one can tell which pairs it matches by whether there is flow going through the edge $(u,v)$ (if there is, this forces the flow through $(s,u)$ and $(v,t)$ as well as the flow through $(u,v)$ to be 1). The total flow $x$ is the number of such matched pairs. This is slightly less obvious than in your original construction, but still true. This gives you (1).
On the other hand, any finite weight cut will contain only edges of the form $(s,u)$ and $(v,t)$ (which each have weight $1$). Check (for (2) and (3)) that a vertex cover corresponds a cut which contains $(s,u)$ for every $u \in V_1$ in the vertex cover, and $(v,t)$ for every $v \in V_2$ in the vertex cover.
After this you are done by the min-cut max-flow theorem.