Page 688 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 667

35. How many vertices and how many edges do these graphs 49. How many subgraphs with at least one vertex does K 3
have? have?
a) K n b) C n c) W n 50. How many subgraphs with at least one vertex does W 3
d) K m,n e) Q n have?
The degree sequence of a graph is the sequence of the de- 51. Draw all subgraphs of this graph.
grees of the vertices of the graph in nonincreasing order. For
example, the degree sequence of the graph G in Example 1 is a b
4, 4, 4, 3, 2, 1, 0.
36. Find the degree sequences for each of the graphs in
Exercises 21–25.
37. Find the degree sequence of each of the following
graphs.
c d
a) K 4 b) C 4 c) W 4
d) K 2,3 e) Q 3 52. Let G be a graph with v vertices and e edges. Let M be
38. What is the degree sequence of the bipartite graph K m,n the maximum degree of the vertices of G, and let m be
where m and n are positive integers? Explain your answer. the minimum degree of the vertices of G. Show that
39. What is the degree sequence of K n , where n is a positive a) 2e/v ≥ m. b) 2e/v ≤ M.
integer? Explain your answer. A simple graph is called regular if every vertex of this graph
40. How many edges does a graph have if its degree sequence has the same degree. A regular graph is called n-regular if
is 4, 3, 3, 2, 2? Draw such a graph. every vertex in this graph has degree n.
41. How many edges does a graph have if its degree sequence 53. For which values of n are these graphs regular?
is 5, 2, 2, 2, 2, 1? Draw such a graph.
a) K n b) C n c) W n d) Q n
A sequence d 1 ,d 2 ,...,d n is called graphic if it is the degree
sequence of a simple graph. 54. For which values of m and n is K m,n regular?
42. Determine whether each of these sequences is graphic. 55. How many vertices does a regular graph of degree four
For those that are, draw a graph having the given degree with 10 edges have?
sequence. In Exercises 56–58 find the union of the given pair of simple
a) 5, 4, 3, 2, 1, 0 b) 6, 5, 4, 3, 2, 1 c) 2, 2, 2, 2, 2, 2 graphs. (Assume edges with the same endpoints are the same.)
d) 3, 3, 3, 2, 2, 2 e) 3, 3, 2, 2, 2, 2 f) 1, 1, 1, 1, 1, 1 56. a
g) 5, 3, 3, 3, 3, 3 h) 5, 5, 4, 3, 2, 1
43. Determine whether each of these sequences is graphic. f b f b
For those that are, draw a graph having the given degree
sequence.
a) 3, 3, 3, 3, 2 b) 5, 4, 3, 2, 1 c) 4, 4, 3, 2, 1 e c
d) 4, 4, 3, 3, 3 e) 3, 2, 2, 1, 0 f) 1, 1, 1, 1, 1
∗ 44. Suppose that d 1 ,d 2 ,...,d n is a graphic sequence. Show d d
57. a
that there is a simple graph with vertices v 1 , v 2 ,..., v n b a f b
such that deg(v i ) = d i for i = 1, 2,...,n and v 1 is adja-
cent to v 2 ,..., v d 1 +1 .
∗ 45. Show that a sequence d 1 ,d 2 ,...,d n of nonnegative inte- e e
gers in nonincreasing order is a graphic sequence if and
only if the sequence obtained by reordering the terms
of the sequence d 2 − 1,...,d d 1 +1 − 1,d d 1 +2 ,...,d n so c d c g d
that the terms are in nonincreasing order is a graphic 58. a b a e
sequence.
∗ 46. Use Exercise 45 to construct a recursive algorithm for de-
h
termining whether a nonincreasing sequence of positive
integers is graphic.
47. Show that every nonincreasing sequence of nonnegative
c d f g
integers with an even sum of its terms is the degree se-
59. The complementary graph G of a simple graph G has
quence of a pseudograph, that is, an undirected graph
the same vertices as G. Two vertices are adjacent in G if
where loops are allowed. [Hint: Construct such a graph
by first adding as many loops as possible at each vertex. and only if they are not adjacent in G. Describe each of
Then add additional edges connecting vertices of odd these graphs.
degree. Explain why this construction works.] a) K n b) K m,n c) C n d) Q n
48. How many subgraphs with at least one vertex does K 2 60. If G is a simple graph with 15 edges and G has 13 edges,
have? how many vertices does G have?