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 ππΊ
(π).