Page 686 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 665

Solution: The vertex set of the union G 1 ∪ G 2 is the union of the two vertex sets, namely,
{a, b, c, d, e, f }. The edge set of the union is the union of the two edge sets. The union is
displayed in Figure 16(b).

Exercises

In Exercises 1–3 find the number of vertices, the number of 10. For each of the graphs in Exercises 7–9 determine the
edges, and the degree of each vertex in the given undirected sum of the in-degrees of the vertices and the sum of the
graph. Identify all isolated and pendant vertices. out-degrees of the vertices directly. Show that they are
both equal to the number of edges in the graph.
1. a b c 11. Construct the underlying undirected graph for the graph
with directed edges in Figure 2.
12. What does the degree of a vertex represent in the acquain-
tanceship graph, where vertices represent all the people
in the world? What does the neighborhood a vertex in this
graph represent? What do isolated and pendant vertices
f e d
in this graph represent? In one study it was estimated that
2. a b the average degree of a vertex in this graph is 1000. What
does this mean in terms of the model?
13. What does the degree of a vertex represent in an academic
collaboration graph? What does the neighborhood of a
vertex represent? What do isolated and pendant vertices
c represent?
e d
14. What does the degree of a vertex in the Hollywood graph
3. a b c d represent? What does the neighborhood of a vertex repre-
sent?Whatdotheisolatedandpendantverticesrepresent?
15. What do the in-degree and the out-degree of a vertex in a
telephone call graph, as described in Example 4 of Sec-
tion 10.1, represent? What does the degree of a vertex in
f i h g e the undirected version of this graph represent?
4. Find the sum of the degrees of the vertices of each graph 16. What do the in-degree and the out-degree of a vertex in
in Exercises 1–3 and verify that it equals twice the number theWeb graph, as described in Example 5 of Section 10.1,
of edges in the graph. represent?
5. Can a simple graph exist with 15 vertices each of degree 17. What do the in-degree and the out-degree of a vertex in a
five? directed graph modeling a round-robin tournament rep-
resent?
6. Show that the sum, over the set of people at a party, of 18. Show that in a simple graph with at least two vertices
the number of people a person has shaken hands with, is there must be two vertices that have the same degree.
even. Assume that no one shakes his or her own hand.
19. Use Exercise 18 to show that in a group of people, there
In Exercises 7–9 determine the number of vertices and edges must be two people who are friends with the same number
and find the in-degree and out-degree of each vertex for the of other people in the group.
given directed multigraph.
20. Draw these graphs.
7. 8. a
b b a) K 7 b) K 1,8 c) K 4,4
d) C 7 e) W 7 f) Q 4
a
In Exercises 21–25 determine whether the graph is bipartite.
You may find it useful to apply Theorem 4 and answer the
question by determining whether it is possible to assign either
red or blue to each vertex so that no two adjacent vertices are
d c d c assigned the same color.
9. a b 21. a b 22. b c

e a d

c d e
d c e