*This set is due Thursday, September 19.*

- 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. - Do exercise 1.1.11 on page 15. (Maximum clique and maximum independent set in a particular graph.)
- Do exercise 1.1.13 on page 15. Let
`G`be the graph whose vertex set is the set of_{k}`k`-tuples with coordinates`{0,1},`with`x`adjacent to`ye`when`x`and`y`differ in exactly one position. Determine whether`G`is bipartite._{k}For example, when k=4, the

`G`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)._{k} - Define the Fibonacci numbers
`a`_{0}=0

a_{1}=1(when

a_{n}= a_{n-1}+ a_{n-2}`n`is at least`2`)`n`is`a`even? Use induction to prove your answer._{n}Your statement to prove should be of the form, ``

`a`is even if and only if ...''. You'll need two base cases,_{n}`n=0`and`n=1`.