# Dilworth's Theorem Implies Konig's Theorem

An excercise says "deduce Konig's Theorem on bipartite graphs from Dilworth's theorem on posets".

Let G be a bipartite graph, G=(A,B). Order the edges left to right. A maximum antichain is a largest independent set in the graph.

I can see a maximum antichain must have every vertex in G incident with it. But it doesn't follow that every edge is incident with it. That may not be true.

So how does one proceed?

• There's a little book by Reichmeider that goes into this and related matters in great detail. Unfortunately, the book is long out of print, but some libraries have it. Aug 10, 2013 at 6:15

## 2 Answers

Create a poset by setting $a \le b$ for every $a \in A$ and $b \in B$ such that $ab \in E(G)$. Let any two elements in $A$ or $B$ be incomparable. In other words, orient each edge so that it goes from $A$ to $B$ and make a partial order based off of this orientation.

Dilworth's Theorem: the minimum cardinality of a collection of chains with union $G$ is the maximum cardinality of an antichain.

Recall that each chain must include $1$ or $2$ members, and we want as many chains with $2$ members as possible. Thus a minimum collection of chains with union $G$ contains a maximum matching and any leftover vertices.

An antichain here is the complement of a vertex cover. It contains no edges, so its complement must meet all edges. Making an antichain maximum makes the vertex cover a minimum.

The rest is just arithmetic.

View any n-node bipartite graph G as a bipartite poset. The nodes of one part are maximal elements, and nodes of the other part are minimal. Every vertex disjoint path covering of the poset of size n-k uses k chains of size 2, which is actually a matching. Each antichain of size n-k corresponds to an independent set in G, and the rest of k nodes forms a vertex cover.