MCS-236 Homework 2

This set is due Thursday, September 19.

1. Do exercise 1.1.4 on page 15. From the definition of isomorphism, prove that G and H are isomporphic if and only if their complements are.

2. Do exercise 1.1.11 on page 15. (Maximum clique and maximum independent set in a particular graph.)

3. Do exercise 1.1.13 on page 15. Let G_k be the graph whose vertex set is the set of k-tuples with coordinates {0,1}, with x adjacent to ye when x and y differ in exactly one position. Determine whether G_k is bipartite.

   For example, when k=4, the G_k has 16 vertices. An example of a vertex in the graph is the 4-tuple (0,1,1,0), which is adjacent to the four vertices (1,1,1,0), (0,0,1,0), (0,1,0,0), and (0,1,1,1).

4. Define the Fibonacci numbers

   a₀=0
   a₁=1
   a_n = a_n-1 + a_n-2      (when n is at least 2)

   For which values of n is a_n even? Use induction to prove your answer.

   Your statement to prove should be of the form, ``a_n is even if and only if ...''. You'll need two base cases, n=0 and n=1.