Math 2602  B1, B2                                                                        Homework  #8
                                             Due Tuesday, March 8, 2005




    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 graph with vertices { 1 , 2 , . . . , 6 } , where { i , j } is an edge unless  i + j = 6 .

     ii)  G  is the graph with vertices { 1 , 2 , . . . , 8 } , where { i , j } is an edge if  i + j  is odd.

    iii)  G  is the graph with vertices { 1 , 2 , . . . , 8 } , where { i , j } is an edge if  i + j  is even.