Math 2602  A1 - A3                                                                             Homework  #7
                                             Due Thursday, October 20, 2005


DEFINITIONS

 A simple graph has no "loops" or "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 no two vertices in the same set are
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 7 vertices and 9 edges must be connected.

  ii) A simple graph with 7 vertices and 5 edges can not be connected.

 iii) A simple graph with an even number of vertices must have a vertex of even degree.

  iv) A simple graph with an odd number of vertices must have a vertex of odd degree.

  v)  A simple bipartite graph with 9 vertices has at most 20 edges.

 vi)  Every bipartite graph is connected.