Math 2602  B1,B2                                                                             Homework  #8
                                         Due Thursday, October 21, 2004



 1.  In each case, find the chromatic number of the graph  G  , determine whether or not  G  has an
      Eulerian cycle , and whether or not  G  is planar.

     i)  G  is the complete graph  K₁₀  minus one edge.

    ii)  G  is the complete bipartite graph  K_4,4 .

   iii)  G  is the graph with vertices { 1 , 2 , . . . , 6 } , where { i , j } is an edge  unless both i and j
         are odd integers.