Math 2602  A1 - A3                                                                       Homework  #8
                                               Due Thursday, October 27


    a)  Suppose a graph is obtained by deleting two edges from the complete bipartite graph  K_4,4 .
.        Can this be done so that

         i) the resulting graph is Eulerian?

        ii) the resulting graph is planar?



    b)  Suppose a graph is obtained by deleting 3 edges from the complete graph  K₆ .
        
         i)  Can this be done so that the resulting graph is Eulerian?

         ii) What is the smallest chromatic number the resulting graph could have?

         iii) What is the largest chromatic number the resulting graph could have?