To finish the proof, you must also define an injection g of G into E, using the condition on the subsets of G and Dilworth's Theorem.
Then for each element a∈G \ f(E), you can redefine f so that a∈ f(E), using the injection g as follows :
Build a set of elements a0, a1, ... of G so that a0 = a and ai = g(f(ai-1)) for i>0.
Let j be the smallest integer so that aj does not belong to G (its existence has to be proved, though).
Redefine f so that f(g(ai)) = ai for each i < j.
The new f is still an injection of E into F such that f(x) ∈ A(x) for each x ∈ E, and besides, a∈ f(E).
Repeat this for each element of G \ f(E) and the problem is solved.
Hope I did not go wrong somewhere. Excuse my poor english, I'm French !
Regards
Alexis
These notes contain a proof. The digraph used in this proof is a little more complicated than the one that you have in mind: each point of the partial order corresponds to two vertices of the digraph.
Let $\langle P,\preceq\rangle$ be the partially ordered set; I’ll write $p\prec q$ to indicate that $p\preceq q$ and $p\ne q$. For each $p\in P$ the digraph $D$ will have two vertices, $p^-$ and $p^+$; in addition, it will have a source vertex $s$ and a sink vertex $t$. For each $p\in P$, $D$ has edges $\langle s,p^-\rangle$ and $\langle p^+,t\rangle$; in addition, for each$p,q\in P$ with $p\prec q$ it has $\langle p^-,q^+\rangle$. Each edge has capacity $1$.
Let $f$ be a maximal flow in $D$, and let $\langle S,T\rangle$ be a minimal cut constructed by the Ford-Fulkerson algorithm. Note that every path from $s$ to $t$ has the form $s\to p^-\to q^+\to t$ for some $p,q\in P$ with $p\prec q$; thus $|f|$ is the number of $p\in P$ such that $f(s,p^-)=1$ there is a $q\in P$ such that $f(p^-,q^+)=1$. Let $C=\{p\in P:f(s,p^-)=0\}$; for future reference note that $|C|=|P|-|f|$.
If $p\in P\setminus C$, then $f(s,p^-)=1$, and there must therefore be a unique ‘successor’ $\sigma(p)\in P$ such that $f(p^-,\sigma(p)^+)=1$, and hence $p\prec\sigma(p)$. Thus, for each $p\in P$ there is a well-defined chain $$p=p_0\prec p_1\prec\ldots\prec p_n\in C$$ in $P$ such that $p_{k+1}=\sigma(p_k)$ for $k=0,\dots,n-1$. ($P$ is finite, so each chain must terminate, and the elements of $C$ are the only elements without successors.) For $p\in P\setminus C$ let $\xi(p)$ be the unique element of $C$ at which the chain from $p$ terminates, and let $\xi(p)=p$ for $p\in C$; then $$\Big\{\{p\in P:\xi(p)=q\}:q\in C\Big\}$$ partitions $P$ into $|C|$ chains. To complete the proof we must show that $P$ also has an antichain of cardinality $|C|$.
The desired antichain is $A=\{p\in P:p^-\in S\text{ and }p^+\in T\}$. Proving that it’s an antichain isn’t too hard. Suppose that $p,q\in A$ with $p\ne q$. Then $p^-\in S$ and $q^+\in T$, so $f(p^-,q^+)\ne0$: either $\langle p^-,q^+\rangle$ isn’t an edge of $D$ at all, or $f(p^-,q^+)=1$, and I leave it to you to show that the latter is impossible: it would unbalance the flow at $p^-$. (The argument here uses the hypothesis that the minimal cut was constructed using the F-F algorithm.) It follows that $p\not\preceq q$, and by symmetry (or a similar argument) $q\not\preceq p$. Thus, $A$ is an antichain.
The last step is to show that the edges contributing capacity towards $c(S,T)$ are preciesly the edges $\langle s,p^-\rangle$ and $\langle p^+,t\rangle$ such that $p\notin A$; this also uses the hypothesis that the minimal cut was constructed using the F-F algorithm, to show that there are no edges of the form $\langle p^-,q^+\rangle$ with $p^-\in S$ and $q^+\in T$.
Once you’ve worked out these details, you’ll have shown that $c(S,T)=|P|-|A|$ and hence that $|A|=|P|-c(S,T)=|P|-|f|=|C|$, as desired.
Best Answer
A maximal chain is one that cannot be extended any more. That means any other element you add to a maximal chain will never result in a longer chain. The above proof is by induction on the size of the poset $P$. The idea is to remove a maximal chain $C$ from $P$ to have a smaller poset. Then use the induction hypothesis.