Questions on proof of Konigs theorem.

The Theorem: Let $G=(V,E)$ be a bipartite graph, then the cardinality of a maximum matching equals the cardinality of a minimum vertex cover.

In the text I found this is proven using the max-flow min-cut theorem, which I don't really understand.

Proof: Let the bipartition be given by $X,Y$. $(1)$ Construct graph $G_0:=(V_0,E_0)$ such that $V_0=V \cup \{s,t\}$ and let $E_0$ contain $E$ as well as new edges leading from $s$ to every vertex in $X$ and also from every vertex in $Y$ to $t$. Define capacity $c$ such that the added edges have capacity $\infty$ and the edges of $E$ have capacity $1$.

$(Q1)$ Why can I have infinite capacity? A capacity function is defined to have values in $\mathbb{R}_+$. Is there a workaround?

$(2)$ Given a matching of cardinality $k$, there exists a flow of value $k$. Furthermore every flow of value $k$ must have a matching of cardinality $k$.

$(Q2)$ Why is this the case? I think that given a matching $M$ a flow of value $|M|$ can be constructed the following way: for $(a,b)$ in $M$ define $f(a,b)=1=f(s,a)=f(b,t)$ and $0$ for all other edges. This should then result in a flow that has value $|M|$. How can I see the other correspondence? I think one also needs to care to make this statement precisely about flows with values in $\mathbb{N}$ instead of arbitrary flows.

$(3)$ Show correspondence of cardinality of vertex covers and cuts. If $W$ is a vertex cover covering $r$ vertices, as well as $W(X)=W \cap X, W(Y)= W \cap Y$, define $$X':=X - W(X), Y':=Y-W(Y).$$ Let $$S:=\{s\} \cup W(Y) \cup Y', T:=\{t\} \cup W(X) \cup Y'$$ (is there a typo here? It seems weird to have $Y'$ twice here). Then $(S,T)$ is a cut with cardinality $r$ (Why does $(S,T)$ have cardinality $r$?). Conversely a cut $(S,T)$ with value $r$ must have $r$ arcs because of the infinity value of the capacity. (This is where the workaround is also important, does it still work without infinity?) If $W$ denotes the union of the vertices $x \in X$ such that $(s,x) \in (S,T)$ and $y \in Y$ such that $(y,t) \in (S,T)$, then $W$ has $r$ vertices.

$(Q3)$ Why does $W$ (as in the last line) give me the corresponding covering?

Thank you in advance for any help!

Solution 1:

The correct construction of the max-flow problem

The proof you found is mistaken. The correct construction is exactly backwards: we want to define the capacity to be $\infty$ for the edges of $E$, and we want the added edges to have capacity $1$. If you do this wrong, you will just get a max-flow problem that counts the edges in your graph.

Also, it is important to point out that max-flow problems are defined for directed graphs, so we should specify how $G_0$ is directed. The rule is:

1. We have already said that the added edges are oriented from $s$ to $X$, and from $Y$ to $t$, so that $s$ is a source and $t$ is a sink.
2. All edges of $E$ are oriented from $X$ to $Y$.

If we want to avoid $\infty$, it is enough to make the capacity of the original edges be $|X|+1$ or something similarly large. Actually, the max-flow problem will work even if all the capacities are $1$, but it will be easier on us in the proof if the original edges have large capacity.

Flows and matchings

You are right about how we construct a flow $f$, given a matching $M$. Going the other way, we must first invoke the result that in a network where all capacities are integers, there is an integer max flow. Also, in our case, the integer max flow is a $\{0,1\}$-valued max flow: none of the edges of $E$ can have flow bigger than $1$, because each vertex in $X$ has at most $1$ flow going in. (This is why we can assign $1$ to all capacities and still have an equivalent max-flow problem.)

Now, if $f$ is an integer max flow, define $M = \{ab \in E : a \in X, b \in Y, f(a,b) = 1\}$.

• This is a matching. If $f(a,b) = f(a,b')=1$, then $a$ has out-flow $2$, but it can only have in-flow at most $1$: contradiction. Similarly, if $f(a,b) = f(a',b)= 1$, then $b$ has in-flow $2$ but out-flow at most $1$.
• The value of $f$ is equal to $|M|$. That's because the value of $f$ is equal to the sum of the flows across any cut; in particular, it is equal to the sum of the flows from $\{s\} \cup X$ to $Y \cup \{t\}$. All those flows are equal to $0$ or $1$, so their sum is the number of them equal to $1$; this is exactly $|M|$.

Cuts and vertex covers

If $W$ is a vertex cover with $|W|=r$, we want to construct a cut with capacity $r$. (For me, a cut is a partition $(S,T)$ of $V(G_0)$ with $s \in S$ and $t \in T$, and its capacity is the total capacity of edges $(a,b)$ with $a \in S$ and $b \in T$. Your definitions may vary slightly, but they should be equivalent.)

The correct definition of the cut with capacity $r$ is $$ S = \{s\} \cup X' \cup W(Y) \qquad T = W(X) \cup Y' \cup \{t\} $$ so yes, there's a typo. The idea is that by definition of a vertex cover, $G$ must not have any edges between $X'$ and $Y'$. So the only edges going from $S$ to $T$ in $G_0$ are:

• Edges from $s$ to $W(X)$, whose total capacity is $|W(X)|$.
• Edges from $W(Y)$ to $t$, whose total capacity is $|W(Y)|$.

We have $|W(X)|+|W(Y)| = |W| = r$, so we have found the cut with capacity $r$.

It is not true that all cuts with capacity $r$ correspond to vertex covers of cardinality $r$. This will be true when $r<\infty$ (if we set the edges of $E$ to have capacity $\infty$) or when $r \le |X|$ (if we set the edges of $E$ to have capacity $|X|+1$). Note that either way, there is at least one such cut: the cut with $S = \{s\}$ and $T = X \cup Y \cup \{t\}$. Therefore the correspondence works for the minimum cut, which is all we want.

In this case, we are looking at a cut $(S,T)$ such that none of the edges of $E$ cross from $S$ to $T$: that's because even one of those edges has higher capacity than $r$. The proof you found is correct about how to get $W$ from $(S,T)$, but to be concrete, I'll spell it out. Define:

• $X' = S \cap X$ and $W(Y) = S \cap Y$, so that $S = \{s\} \cup X' \cup W(Y)$ as we had earlier.
• $W(X) = X \cap T$ and $Y' = Y \cap T$, so that $T = W(X) \cup Y' \cup \{t\}$ as we had earlier.

Because there are no edges of $E$ between $S$ and $T$, there are no edges between $X'$ and $Y'$, so all edges are incident to either $W(X)$ or $W(Y)$ or both. This means $W = W(X) \cup W(Y)$ is in fact a vertex cover.

The capacity of $(S,T)$ is exactly $|W(X)| + |W(Y)| = |W|$. So we have gone from a cut of capacity $r$ to a vertex cover of cardinality $r$.