Math 2602  B1,B2                                                                        Homework  #7
                                           Due Tuesday, March 1, 2005

    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 split into two sets so that two vertices in the same set are never
    joined by an edge.

    A graph is connected if each pair of vertices are joined by (at least one) path.

    a graph is complete if each pair of edges are joined by an edge.


   1.  Determine whether the statement is true or false.

      i)  A simple graph with an odd number of vertices must have an odd number of edges






     ii)  Every simple connected graph has more vertices than edges.






     iii) There is a simple bipartite graph with 11 vertices and 30 edges.






     iv)  There is a simple graph with vertex degrees 2 , 2 , 2 , 3 , 3 , 5 .







     v)  The complete graph on n vertices has  n(n+1)/2  edges.