1. (This is a graph theory question. Do not put Data. You must prove using graph theory) Place n points on a cycle, where n 2k + 1 and k 1. Let be the 2k-regular graph obtained by joining each point to the k nearest points in each direction on the circle.

a) Prove that if n k(k+1), then (Gn,k) = k+1 when k+1 divides n, and (Gn,k) = k+2 when k + 1 does not divide n (Note: X is the chromatic number)

b) Prove that (Gn,k) > k+2 for n=k(k+1)1 and k2.