Let Xn = f1;2;3; :::;ng. For any n 1 and k n, we create the following simple graph Gn;k: The vertices of Gn;k are the subsets of Xn of size k.
Two vertices are adjacent if their corresponding subsets in Xn are disjoint.
(a) Draw G5;2. Label your vertices by the subsets of X5 of size 2.
(b) Find a formula, in terms of n and k, for the number of vertices and for the number of edges in Gn;k.
(c) Show that c(Gn;k) n by showing a way to properly colour the vertices of Gn;k using n colours.