by disjoint chains since is an antichain of size in . Thus, can be covered by disjoint chains, as required. Next, if for each , then is an antichain of size in (since is maximal in ). Now can be covered by the chains , completing the proof. Proof via Kőnig's theorem Like a number of other results in combinatorics, Dilworth's theorem is equivalent to Kőnig's theorem on bipartite graph matching and several other related theorems including Hall's marriage theorem . To prove Dilworth's theorem for a partial order S with n elements, using Kőnig's theorem, define a bipartite graph G = (U,V,E) where U = V = S and where (u,v) is an edge in G when u < v in S. By Kőnig's theorem, there exists a matching M in G, and a set of vertices C in G, such that each edge in the graph contains at least one vertex in C and such that M and C have the same cardinality m. Let A be the set of elements of S that do not correspond to any vertex in C; then A has at least n - m elements (possibly more if C contains vertices corresponding to the same element on both sides of the bipartition) and no two elements of A are comparable to each other. Let P be a family of chains formed by including x and y in the same chain whenever there is an edge (x,y) in M; then P has n - m chains. Therefore, we have constructed an antichain and a partition into chains with the same cardinality. To prove Kőnig's theorem from Dilworth's theorem, for a bipartite graph G = (U,V,E), form a partial order on the vertices of G in which u < v exactly when u is in U, v is in V, and there exists an edge in E from u to v. By Dilworth's theorem, there exists an antichain A and a partition into chains P both of which have the same size. But the only nontrivial chains in the partial order are pairs of elements corresponding to the edges in the graph, so the nontrivial chains in P form a matching in the graph. The complement of A forms a vertex cover in G with the same cardinality as this matching. This connection to bipartite matching allows the width of any partial order to