Page 687 - Discrete Mathematics and Its Applications

666 10 / Graphs

23. b c c) Is the matching of responsibilities you found in part
(b) a complete matching? Is it a maximum matching?

a d 29. Suppose that there are five young women and five young
men on an island. Each man is willing to marry some of
the women on the island and each woman is willing to
f e marry any man who is willing to marry her. Suppose that
24. a b Sandeep is willing to marry Tina and Vandana; Barry is
willing to marry Tina, Xia, and Uma; Teja is willing to
marry Tina and Zelda; Anil is willing to marry Vandana
f c and Zelda; and Emilio is willing to marry Tina and Zelda.
Use Hall’s theorem to show there is no matching of the
young men and young women on the island such that each
young man is matched with a young woman he is willing
e d
to marry.
25. b
30. Suppose that there are five young women and six young
men on an island. Each woman is willing to marry some
a c
of the men on the island and each man is willing to marry
any woman who is willing to marry him. Suppose that
Anna is willing to marry Jason, Larry, and Matt; Barbara
is willing to marry Kevin and Larry; Carol is willing to
f d
marry Jason, Nick, and Oscar; Diane is willing to marry
Jason, Larry, Nick, and Oscar; and Elizabeth is willing to
e marry Jason and Matt.
26. For which values of n are these graphs bipartite?
a) Model the possible marriages on the island using a
a) K n b) C n c) W n d) Q n
bipartite graph.
27. Suppose that there are four employees in the computer b) Find a matching of the young women and the young
support group of the School of Engineering of a large men on the island such that each young woman is
university. Each employee will be assigned to support matched with a young man whom she is willing to
one of four different areas: hardware, software, network- marry.
ing,andwireless. SupposethatPingisqualifiedtosupport c) Is the matching you found in part (b) a complete
hardware,networking,andwireless;Quiggleyisqualified matching? Is it a maximum matching?
to support software and networking; Ruiz is qualified to
support networking and wireless, and Sitea is qualified to ∗ 31. Suppose there is an integer k such that every man on a
support hardware and software. desert island is willing to marry exactly k of the women
on the island and every woman on the island is willing to
a) Use a bipartite graph to model the four employees and
marry exactly k of the men. Also, suppose that a man is
their qualifications.
willing to marry a woman if and only if she is willing to
b) Use Hall’s theorem to determine whether there is an
assignment of employees to support areas so that each marry him. Show that it is possible to match the men and
employee is assigned one area to support. women on the island so that everyone is matched with
c) If an assignment of employees to support areas so that someone that they are willing to marry.
each employee is assigned to one support area exists, ∗ 32. In this exercise we prove a theorem of Øystein Ore.
find one. Suppose that G = (V, E) is a bipartite graph with bipar-
28. Supposethatanewcompanyhasfiveemployees:Zamora, tition (V 1 ,V 2 ) and that A ⊆ V 1 . Show that the maximum
Agraharam, Smith, Chou, and Macintyre. Each employee number of vertices of V 1 that are the endpoints of a
will assume one of six responsiblities: planning, public- matching of G equals |V 1 |− max A⊆V 1 def(A), where
ity, sales, marketing, development, and industry relations. def(A) =|A|−|N(A)|. (Here, def(A) is called the de-
Each employee is capable of doing one or more of these ficiency of A.) [Hint: Form a larger graph by adding
jobs: Zamora could do planning, sales, marketing, or in- max A⊆V 1 def(A) new vertices to V 2 and connect all of
dustry relations; Agraharam could do planning or devel- them to the vertices of V 1 .]
opment; Smith could do publicity, sales, or industry re- 33. For the graph G in Exercise 1 find
lations; Chou could do planning, sales, or industry rela-
tions; and Macintyre could do planning, publicity, sales, a) the subgraph induced by the vertices a, b, c, and f .
or industry relations. b) the new graph G 1 obtained from G by contracting the
edge connecting b and f .
a) Model the capabilities of these employees using a bi-
partite graph. 34. Let n be a positive integer. Show that a subgraph induced
b) Find an assignment of responsibilites such that each by a nonempty subset of the vertex set of K n is a complete
employee is assigned one responsibility. graph.