CPTS553 Assignment5 Solved

Description

 

1. The dodecahedron graph 𝐺 is depicted below:
2. Determine, with justification, whether 𝐺 is Eulerian.
3. Show that 𝐺 is Hamiltonian by finding a Hamilton cycle.
4. Let 𝐻 be the graph depicted to the right: A. Find a 4-coloring of 𝐻.
5. Show that no 3-coloring of 𝐻 exists.
6. The graph 𝑃₃×𝑃₃ 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?
7. Find the chromatic polynomial 𝑝_𝐺(𝑘)of 𝐺 =𝐶₆ and determine whether 𝑘−2 is a factor of 𝑝_𝐺(𝑘).