Math 2602  B1, B2                                                                                Homework #7

                                            Due Thursday, October 16, 2003

 1.  For each graph find the "clique number" (p. 211) and the "chromatic number" (p.257).

   i)  The graph obtained by deleting one edge from the complete graph  K₁₀ .

   ii) The complete bipartite graph  K_6,5 . (see p.214)

  iii) The graph whose vertices are the integers 1 ,  2 ,  3 ,  .  .  .  ,  8 , in which vertices i and j
        are adjacent if  i + j  is not a multiple of 3 or of 4.  (e.g., 2 and 3 are adjacent, but  2 and
        4 are not since 2 + 4 = 2*3, and 3 and 5 are not since 3 + 5 = 2*4.)