Please only work on this yourself, but if you can use any books or references, please cite them clearly, but put your answer in your own words.

This is due at my office 433 Malott Hall on Friday, December 17, 2004 at 4 PM.  Good luck.

Let G be a finite (simple) graph with n vertices, let p(G,x) be the number of ways of coloring the vertices of G such that adjacent vertices have distinct colors using at most x colors.  

1.  Show that p(K_n,x)=x(x-1)(x-2)...(x-n+1), where K_n is the complete graph on n vertices.

2.  Suppose that a and b are non-adjacent vertices of G,  H_1 is G with a and b identified and H_2 is G with the edge [a,b] added.  Show that p(G,x)= p(H_1,x) + p(H_2,x).  Use this to show that any p(G,x) is a polynomial in x.

3.  Show that p(G,x) = x(x-1)^(n-1) if and only if G is a tree.

4.  Use the Moebius function to show that the coefficients of p(G,x) alternate in sign.  

5.  Let F_n be the n-th Fibbonacci number (where F_0=0, F_1=1, and F_(n+1)=F_n+F_(n-1)).  Find an expression for F_n of the form F_n = c_1a^n +c_2b^n, where a, b, c_1, c_2 are constants.  (Hint: Use generating functions.)

6.  Problem 14G in Van Lint and Wilson.

7. Let F denote a finite field with q elements. .  Suppose that you choose a monic polynomial p(x) of degree n at random with uniform probability.  What is the probability that p(x) is irreducible in F[x]?  When n= 8, for which finite field is the probability of choosing an irreducible monic polynomial the smallest, and what is that probability?