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 ๐๐บ
(๐).
