Maximum Independent Set of a Bipartite Graph I'm trying to find the Maximum Independent Set of a Biparite Graph.

I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow":


  Problem:
  
  Given a bipartite graph $G = (U,V,E)$, find an independent set $U' \cup V'$ which is as large as possible, where $U' \subseteq U$ and $V' \subseteq V$. A set is independent if there are no edges of $E$ between
  elements of the set.
  
  Solution:
  
  Construct a flow graph on the vertices $U \cup V \cup \{s,t\}$. For
  each edge $(u,v) \in E$ there is an infinite capacity edge from $u$ to
  $v$. For each $u \in U$, there is a unit capacity edge from $s$ to $u$,
  and for each $v \in V$, there is a unit capacity edge from $v$ to
  $t$.
  
  Find a finite capacity cut $(S,T)$, with $s \in S$ and $t \in T$. Let
  $U' = U \cap S$ and $V' = V \cap T$. The set $U' \cup V'$ is
  independent since there are no infinite capacity edges crossing the
  cut.  The size of the cut is $|U - U'| + |V - V'| = |U| + |V| - |U' \cup V'|$. This, in order to make the independent set as large as
  possible, we make the cut as small as possible.


So lets take this as the graph:

A - B - C
    |
D - E - F


We can split this into a bipartite graph as follows 
$(U,V)=(\{A,C,E\},\{B,D,F\})$

We can see by brute force search that the sole Maximum Independent Set is $A,C,D,F$. Lets try and work through the solution above:

So the constructed flow network adjacency matrix would be:

$$\begin{matrix}
  &amp; s &amp; t &amp; A &amp; B &amp; C &amp; D &amp; E &amp; F \\
s &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 \\
t &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 1 \\
A &amp; 1 &amp; 0 &amp; 0 &amp; \infty &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
B &amp; 0 &amp; 1 &amp; \infty &amp; 0 &amp; \infty &amp; 0 &amp; \infty &amp; 0 \\
C &amp; 1 &amp; 0 &amp; 0 &amp; \infty &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
D &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; \infty &amp; 0 \\
E &amp; 1 &amp; 0 &amp; 0 &amp; \infty &amp; 0 &amp; \infty &amp; 0 &amp; \infty \\
F &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; \infty &amp; 0 \\
\end{matrix}$$

Here is where I am stuck, the smallest finite capacity cut I see is a trivial one: $(S,T) =(\{s\},\{t,A,B,C,D,E,F\})$ with a capacity of 3.

Using this cut leads to an incorrect solution of:

$$ U' = U \cap S = \{\}$$
$$ V' = V \cap T = \{B,D,F\}$$
$$ U' \cup V' = \{B,D,F\}$$

Whereas we expected $U' \cup V' = \{A,C,D,F\}$?  Can anyone spot where I have gone wrong in my reasoning/working?
The complement of a maximum independent set is a minimum vertex cover.

To find a minimum vertex cover in a bipartite graph, see König's theorem.