Description
1. The dodecahedron graph is depicted below:
-
-
-
Determine, with justification, whether is Eulerian.
-
-
-
-
-
Show that is Hamiltonian by finding a Hamilton cycle.
-
-
-
Let be the graph depicted to the right:
-
-
Find a 4-coloring of .
-
-
-
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?
-
Find the chromatic polynomial ( )of = 6 and determine whether − 2 is a factor of ( ).