Homework 8

1.

 a -- b -- c
 |    |    |
 d -- e -- f
 |    |    |
 g -- h -- i

A lexicographic breadth first search order : abdecgfhi

2. No, it has cycles of length 4 that do not contain a chord

3. Smallest number of colors = ihfgcedba (reverse of lexicographic breadth first search order)
	2 colors
   Non-optimal order = ahbcdefgi
	3 colors

4.

a --- b --- d
  \   |   / |
    \ | /   |
      c --- e

a     |-------|
b         |------|
c        |------------|
d               |------|
e                   |------|