## Description

1. The dodecahedron graph 𝐺 is depicted below:

A. Determine, with justification, whether 𝐺 is Eulerian.

B. Show that 𝐺 is Hamiltonian by finding a Hamilton cycle.

2. Let 𝐻 be the graph depicted to the right:

A. Find a 4-coloring of 𝐻.

B. Show that no 3-coloring of 𝐻 exists.

3. The graph 𝑃3 × 𝑃3

is depicted below. Show that this graph is not

Hamiltonian. One approach: Show that any Hamilton path must

begin and end at even-numbered vertices. Why does this prevent

forming a Hamilton cycle?

4. Find the chromatic polynomial 𝑝𝐺

(𝑘)of 𝐺 = 𝐶6 and determine whether

𝑘 − 2 is a factor of 𝑝𝐺

(𝑘).