Prove König's theorem using Dilworth's theorem I am trying to derive König's theorem from Dilworth's theorem, but it seems like I'm stuck. I know that I have to define some kind of binary relation on the set of a bipartite graph's vertices, then use Dilworth's theorem. However, every relation I've come up with so far either did not satisfy some properties needed for Dilworth's theorem or seemed to be completely useless. Can anyone point me in the right direction?
Thanks.
 A: Try making $a \geq b$ precisely when $a \in A$ is connected to $b \in B$ in the graph, where $A$ and $B$ are the two parts of the vertex set. What can you make from a chain cover of the resulting poset? What can you make from an antichain? You may have to take some complements...
A: There is a very nice (but hard to find) book by Philip F. Reichmeider, The Equivalence of Some Combinatorial Matching Theorems, which discusses König, Dilworth, Hall, max-flow-min-cut, etc., etc., and would be a great reference for your studies. 
A: Dilworth's Theorem relates the size of smallest chain cover to the size of largest antichain. It claims that both the numbers are same. So to use Dilworth's Theorem to  derive König's theorem one need to construct a Partially ordered set from the Bipertite graph. 
You can consider the edges of the bipartite graph as elements of the Partially ordered set (poset). We say two edges are related if they share a common vertices. This yields us the relation R for the poset.


*

*Now a matching in bipartite graph is a collection of disjoint edges. It corresponds to an antichain in the poset. Because no two edges are related. Thus maximum matching corresponds to the largest antichain in the poset. 

*We are now left with proving that a chain cover in the poset somehow corresponds to a vertex cover in the Bipertite graph. Consider a chain C in the poset that we created out of bipartite graph. Its elements are edges such that every pair shares a common vertex. In a bipartite graph this is possible only if all the edges of chain share a common vertex(one can prove it using induction on the size of chain). Therefore for every chain we can get a common vertex. Collect all these vertices for every chain in a single set. It is easy to see that this gives us a collection of vertices that cover all the edges; hence it is a vertex cover. Thus the smallest chain cover corresponds to the minimum vertex cover. 

*This completes the proof because according to Dilworth's theorem smallest chain cover has same size as largest antichain. This is same as saying maximum matching and minimum vertex cover has same size.   

A: First, let us recall the following facts:

*

*In any graph, a subset of vertices is a vertex cover iff its complement is an independent set.


*In any graph, the size of a matching is a lower bound for the minimal size of a vertex cover.
Now, let $G = (V, E)$ be a bipartite graph, i.e., we have a disjoint union $V = V_1 \cup V_2$ such $V_1$ and $V_2$ are independent sets. We want to show that the maximum size of a matching in $G$ equals the minimum size of a vertex cover in $G$ using Dilworth's theorem.
We define a partial order on $V$ by setting $u \le v$ iff $u \in V_1$ and $\{u, v\} \in E$ (which implies $v_2 \in V_2$). By construction, as $G$ is bipartite, any chain has length at most two, i.e., it is either a single edge or a single vertex.
Hence,
\begin{align*}
 |V| & = \mbox{# of single element chains} + 2 \cdot \mbox{# of two element chains} \\
     & = \mbox{size of the chain partition} + \mbox{# of two element chains}.
\end{align*}
If we only take those chains containing precisely two vertices, i.e., the edges, they form a matching. So, with the previous equation,
$$
 |V| - \mbox{size of the chain partition} \le \mbox{maximum size matching}.
$$
By the first fact mentioned above
and as an antichain is precisely an independent set in $G$,
$$
 \mbox{minimum size vertex cover} \le |V| - \mbox{maximum size of an antichain}.
$$
By Dilworth's theorem,
$$
 |V| - \mbox{maximum size of an antichain} = |V| - \mbox{size of the chain partition}.
$$
So, we find,
$$
 \mbox{minimum size vertex cover} \le \mbox{maximum matching}.
$$
By the above mentioned second fact, we have equality. QED
