The illustration below shows a bipartite graph N in which the arcs have been labelled a,...,g. For each of the following partially ordered sets S, illustrate Dilworth's theorem by (1) drawing a picture of the partial ordering, (2) indicating a smallest possible cover by chains, and (3) indicating an antichain of largest possible size. Of course, the size of the antichain should equal the size of the chain covering.

A. Let S be the set of all matchings in N, partially ordered by set inclusion. (For example, {a,g}, {c}, and {a,c,g} are matchings, and the empty set is also a matching. You can write acg instead of {a,c,g} for brevity.)

B. Let S be the set of all trees in N, partially ordered by set inclusion. A tree is a collection of arcs that forms a connected set and contains no cycles. (For example, {a,b}, {a}, and {a,b,g} are trees, but {a,b,d} and {a,c,d,e,f} are not. The empty set is a tree.)

C. Let B denote the set of nodes on the left and let G denote the set of nodes on the right. Let S be the set of all functions mapping a subset of B into G, partially ordered by extension. (For example, {a}, {a,d}, {a,c,e,g} and {c,e} are "functions", but {a,c,d} is not. The empty set is a function. The function {a,d} extends {d} and the function {a,d,f} extends {a,d}. All functions extend the empty function.)