348 CHAPTER^6 Graph Theory
W Exercises
- Find a graph with 12 edges having six vertices of degree three and the remaining
vertices of degree less than three. - Give an example of a graph with at least four vertices, or prove that none exists, such
that:
(a) There are no vertices of odd degree.
(b) There are no vertices of even degree.
(c) There is exactly one vertex of odd degree.
(d) There is exactly one vertex of even degree.
(e) There are exactly two vertices of odd degree. - (a) Construct a graph with six vertices and degree sequence 1, 1, 2, 2, 3, 3.
(b) Construct a graph with six vertices and degree sequence 1, 1, 3, 3, 3, 3.
(c) Can you find at least two graphs with each of these degree sequences? - Construct all degree sequences for graphs with four vertices and no isolated vertex.
- Determine all possible degree sequences for graphs with five vertices containing no
isolated vertex and six edges. - Determine all possible degree sequences for graphs with five vertices containing no
isolated vertex and eight edges. - Let d, d2 ..... d, be a nondecreasing sequence of non-negative integers representing
the degrees of the vertices of some graph. Prove that Z 1 jdi is even. Is the converse
to this result true?- Show that the sequence 2, 2, 2, 3, 3, 4, 5, 5, 6 is graphical. Build an answer from a
graph with degree sequence 1, 1, 1, 1, 1, 1. - For n = 2, 3, 4, 5, determine a relationship between the number of edges and the num-
ber of vertices in an n-regular graph with p vertices where p = 1, 2, 3 ..... Construct
all 3-regular graphs on four and six vertices. - Let G be a graph. Prove that G is bipartite if and only if G contains no odd cycle.
- Draw a graph with 16 vertices labeled with the elements of {0, 1} x {0, 11 x {0, 11 x
10, 1 } and edges that correspond to the edges in Q4. - Prove that Q, where n is some integral power of 2 has 2n vertices and n 2n- - edges.
- Prove that Q, is bipartite for n = 2, 3, 4 ....
- Prove that for any graph G on six vertices, either G or G contains a triangle.
- Construct C 5 , K 3 , 3 , and K 2 , 4.
- For the graphs
b(^2 3) a-
5
14 4 e U V W
G, G2 G3