Math 2602  A1 , A2 , A3                                                                  Homework  #6

                                                     Due Tuesday, February 25, 2003

     DEFINITIONS:

      A simple graph has no "loops" and no "multiple" ("parallel") edges.

     The degree of a vertex is the number of edges for which it is an endpoint.

      A graph is bipartite if its vertices can be divided into two sets so that two vertices in the same
      set are not joined by an edge.

      A graph is complete if each pair of vertices are joined by an edge.

      A graph is connected if each pair of vertices are joined by a path.


   1. Determine whether the statement is true or false.

       i)    A complete (simple) graph with n vertices has 1/2 (n)(n+1) edges.


                                                                                                                         _________    _________
                                                                                                                                 T                   F


       ii)  There exists a simple graph with 6 vertices, which have degrees 1, 2, 2, 3, 4, and 5.


                                                                                                                          _________    _________
                                                                                                                                 T                    F


       iii) There exists a simple graph with 8 vertices, no two of which have the same degree.


                                                                                                                          _________    _________
                                                                                                                                 T                   F

       iv)  A simple bipartite graph with 6 vertices has at most 9 edges.


                                                                                                                          _________    _________
                                                                                                                                  T                   F

       v)   A connected graph with 6 vertices has at least 5 edges.

     
                                                                                                                          _________    _________
                                                                                                                                  T                    F

      vi)  A bipartite graph has an even number of edges.


                                                                                                                          __________    _________
                                                                                                                                  T                    F