Math 2602  B1, B2                                                                              Homework  #7
                                          Due Tuesday, October 12, 2004


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 connected if each pair of vertices are joined by (at least one) path.

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

 1.  Determine whether the statement is true ot false.

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





  ii)  Every simple graph has an even number of vertices of even degree.





  iii) There exists a simple bipartite graph with 8 vertices and 20 edges.





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





  v)  A simple graph on 10 vertices has at most 45 edges.





  vi) There exists a simple connected  graph with 9 vertices and 7 edges.