Mathematics for Computer Science

Chapter 11 Simple Graphs350

Problems for Section 11.7

Class Problems

Problem 11.21.
LetGbe the graph below^11. Carefully explain why.G/D 4.

Homework Problems

Problem 11.22.
Math for Computer Science is often taught using recitations. Suppose it happened
that 8 recitations were needed, with two or three staff members running each recita-
tion. The assignment of staff to recitation sections is as follows:

 R1: Ali, Oshani, Henrique

 R2: Ali, Nick, Kyle

 R3: Oshani, Radhika

 R4: Becky, Nick, Oscar

 R5: Becky, Subha, Kyle

 R6: Subha, Radhika

 R7: Subha, Nick

 R8: Oshani, Radhika, Kyle

Two recitations can not be held in the same 90-minute time slot if some staff
member is assigned to both recitations. The problem is to determine the minimum
number of time slots required to complete all the recitations.

(^11) FromDiscrete Mathematics, Lov ́asz, Pelikan, and Vesztergombi. Springer, 2003. Exercise
13.3.1