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 Gk 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 Gk is bipartite.

    For example, when k=4, the Gk 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
    a0=0
    a1=1

    an = an-1 + an-2
         (when n is at least 2)
    For which values of n is an even? Use induction to prove your answer.

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