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)|$.
Best Answer
In your example the cut is $[\{s\},\{a,b,t\}]$; its capacity is $1$, since the only edge that is cut is $sa$.
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.
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.
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\}$.
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$.