(1) Let G be the nine-vertex grid graph with vertices a, b, c, d, e, f,
g, h, i and edges ab, bc, de, ef, gh, hi, ad, dg, be, eh, cf, and
fi. Find a lexicographic breadth first search ordering for G, starting
from vertex a.

(2) Is the graph G from problem 1 a chordal graph? Why or why not?

(3) Describe an ordering for the vertices of G such that the greedy
coloring algorithm finds the smallest possible number of colors for G,
and another ordering for the vertices of G such that the greedy
algorithm uses too many colors.

(4) Let H be the graph with five vertices a, b, c, d, e, and seven edges
ab, ac, bc, bd, cd, ce, and de. Find a set of five intervals
representing H as an interval graph.