Math 2602  A1 - A3                                                                                        Homework  # 7
                                                    Due Tuesday, March 2, 2004

1.  Let  G  be the (simple) graph with vertices  { 1 , 2 , 3 ,  . . .  , 8  }and the adjacency matrix below.


                                                   1      2      3      4      5      6      7      8

                                            1     0      1      1      0      1      1      0      1
                                            2     1      0      1      0      0      1      1      0
                                            3     1      1      0      1      0      0      1      0
                                            4     0      0      1      0      1      0      1      1
                                            5     1      0      0      1      0      1      0      1
                                            6     1      1      0      0      1      0      1      1
                                            7     0      1      1      1      0      1      0      1
                                            8     1      0      0      1      1      1      1      0

  i)   Find the clique number (p. 211) and the chromatic number (p. 257) of  G .           

  ii)  Does  G have an Euler cycle?  An Euler path?  Explain.

  iii) Is  G  planar?  Explain.

  iv) If  { i , j } is an edge of  G , let its length be  | i - j  | .  Find the total length of a shortest path from
       2 to 8 in  G .