Math 2602 B1 , B2
Homework #6
Due Tuesday, October 7, 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 (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 a path.
Determine whether the statement is true or false.
i) A graph in which each degree is even must have an
even number of vertices.
____________
True or False
ii) If a graph is isomorphic to a bipartite graph, it is bipartite.
____________
iii) There is no simple graph with the degrees 1 , 2 , 3 , 4 , 4
, 4 .
____________
iv) There is no bipartite graph with 7 vertices and
more than 12 edges.
____________
v) Every simple graph with 7 vertices and at least 10 edges
is connected.
____________
vi) Every simple graph with 10 vertices and at least 11 edges has
a vertex of degree
at least 3.
____________