Prove König's theorem using Dilworth's theorem

Question

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.

Answer 1

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...

Answer 2

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.

Answer 3

First, let us recall the following facts:

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

2. 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