Math  A1 - A3                                                                                                 Homework  #6
                                           Due Tuesday ,  February 24 , 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 ("incident" with it) .

A graph is bipartite if its vertices can be divided into two (disjoint) sets so that each edge has
an endpoint in each set.

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 (at least one) path.


1.  Determine whether there is a simple graph of the type described, and if so, find the number
     of edges in such a graph.

   i)   A complete graph with 10 vertices.

  ii)   A graph with degrees  2 , 2 , 3 , 4 , 4 , 4  .

  iii)  A graph with degrees  2 , 2 , 2 , 4 , 4 , 4  .

  iv)  A bipartite graph with degrees  2 , 2 , 2 , 4 , 4  .

  v)   A connected graph with twice as many vertices as edges.