Graph Theory Assignment 5 Solution

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