Proving Konig-Egervary Theorem from Ford-Fulkerson

Question

I've been going over a proof for Konig-Egervary Theorem from Ford Fulkerson, and I just don't see it. In fact, it just seems false. So I'm not sure what I'm missing. Note: the Konig-Egervary Thm says: if $G$ is a bipartite graph, then the max size of a matching in $G$ equals the min size of a vertex cover of $G$.

Setup:

Let $G$ be a bipartite graph with partition $X,Y$. Construct a network $N$ by adding a source $s$ and sink $t$ with edges of capacity 1 from $s$ to each $x\in X$. Also, add an edge of capacity 1 from each $y \in Y$ to $t$. Orient each edge of G from $X$ to $Y$, with infinite capacity.

For concreteness: let N be s -> a -> b> t, where sa = 1, ab = infinity and bt = 1. (From construction above.)

Part of proof that I don't understand:

A minimum cut must have finite capacity, since [$s,V(N) - s]$ is a cut of finite capacity. (Q1: What is [$s,V(N) - s$] for the above example.) Let $[S,T]$ be a min cut in $N$. (Q2: What is the min-cut in $N$?) A cut of finite capacity has no edge of infinite capacity from $S$ to $T$. Hence $G$ has no edge from $S\bigcap T$ to $T \bigcap Y$. (Q3: Why?) This means that ($X-S) \bigcup (Y - T)$ is a set of vertices in G covering every edge of $G$. (Q4: Why? What is $X-S$ for the example $N$ above? What is $Y-T$ for the above $N$?) Furthermore, the cut $[S,T]$ consist of the edges from $s$ to $X\bigcap T = X-S$ and from $Y \bigcap S = Y - T$ to $t$. (Q5: no idea why this is the case. In fact, it seems false.) The capacity of the cut is the number of these edges, which equals $|(X-S) \bigcup (Y-T)|$.

Answer 1

1. In your example the cut is $[\{s\},\{a,b,t\}]$; its capacity is $1$, since the only edge that is cut is $sa$.

2. There are two min cuts in your example, $[\{s\},\{a,b,t\}]$ and $[\{s,a,b\},\{t\}]$, each with capacity $1$. The only other cut is $[\{s,a\},\{b,t\}]$, which has infinite capacity.

3. Your ‘no edge from $S\cap T$ to $T\cap Y$’ should read ‘no edge from $S\cap X$ to $T\cap Y$’. If there were an edge from $S\cap X$ to $T\cap Y$, it would be an edge of $G$ and therefore have infinite capacity. Thus, $[S,T]$ would not be a cut of finite capacity.

4. Suppose that $xy$ is an edge of $G$, where $x\in X$ and $y\in Y$. We just saw there is no edge of infinite capacity from $S$ to $T$, so it’s impossible to have both $x\in S\cap X$ and $y\in T\cap Y$. Thus, either $x\in X\setminus S$, or $y\in Y\setminus T$ (or both), and therefore $(X\setminus S)\cup(Y\setminus T)$ covers $xy$. For the min cut $[\{s\},\{a,b,t\}]$ in your example $X\setminus S=\{a\}$ and $Y\setminus T=\varnothing$; for the other min cut $X\setminus S=\varnothing$ and $Y\setminus T=\{b\}$.

5. Since $[S,T]$ has no edges of infinite capacity, it has none of the edges of the graph $G$. This means that its only edges are edges from $s$ to $X$ and from $Y$ to $t$. Which of those are actually in the cut? Since $s\in S$, the edges from $s$ to $X$ that actually cross the cut are those that run from $s$ to points of $X\cap T$, and of course those are exactly the points of $X$ that are not in $S$, i.e., the points of $X\setminus S$. Similarly, $t\in T$, so the edges from $Y$ to $t$ that cross the cut are the ones from $Y\cap S$ to $t$, which are precisely the ones from $Y\setminus T$ to $t$.

Answer 2

A cut is a partition the vertices of a network into two nonempty sets $A$ and $B$. The capacity of the cut is the sum of the capacities of the (cut) edges between $A$ and $B$. Answer to Q1: $[s,V(N) - s]$ is notation for the cut of the network $N$ into the two sets, one of which is $\{s\}$, and the other of which is $V(N) - \{s\}$. This cuts through a finite number of edges of capacity 1, so the capacity of the cut is finite. Once we know there is any cut with finite capacity, we know that there must be one of minimum capacity. (Every set of non-negative integers has a smallest element.) Answer to Q2: A minimum cut exists, so let $S$ and $T$ be the partition of $V$ that gives a minimum cut.

Answer to Q3: There is a typo in your quote. $S\bigcap T$ should be $S\bigcap X$. Because the partition into $S$ and $T$ is a minimum cut (hence finite capacity), it can contain no infinite-capacity edges. The only infinite-capacity edges in $N$ go from $X$ to $Y$ (as constructed), so none of the edges cut (which are those from $S$ to $T$) also go from $X$ to $Y$.

Answer to Q4: The cut $[S,T]$ removed no edges from $X$ to $Y$, by the previous remark, so none of the edges in $G$ from $X$ to $Y$ ran between $S$ and $T$. Every edge of $G$ either starts outside of $S$, or ends outside of $T$, so every edge of $G$ has something in either $X-S$ or $Y-T$ as an endpoint. Thus the set $(X-S)\bigcup (Y-T)$ meets every edge.

Note that this edge-covering set of vertices (henceforth "cover") does not include either $s$ or $t$.

Answer to Q5: The edges of $N$ cut by $[S,T]$, then, are never between $X$ and $Y$. This means the cut edges must either start at $s$ or end at $t$. Those that start at $s$ must end in $X-S$, because every edge that starts at $s$ ends somewhere in $X$, and the only vertices in the cover (remember, it doesn't contain $s$) that are in $X$ are in $X-S$. The rest of the cut vertices must end at $t$ (again, not in the cover) and begin in $Y$ (by construction) and in the cover (because $t$ wasn't there), so end in $Y-T$.