1 
Aug 24 
1.1, 1.2 
Read the course syllabus and sections 1.1 and 1.2.
An icecream shop has 7 flavors. John visits the icecream shop 3 days in a row, ordering one scoop of icecream each day.
 How many ways can John order icecream?
 How many ways can John order icecream if he orders the same flavor on the first and third days?
 How many ways can John order icecream if he orders different flavors on the first and third days?
 What is the relationship between your answers? Explain.
1.1 and 1.2: 17 (odd), 10, 12, 14(a,b), 15, 20, 23

2 
Aug 31 
1.3, 1.4 
Read sections 1.3 and 1.4.
1.3: 1, 2, 3(a), 4, 713(odd), 15(a), 16(a,d,e), 17(a,b,c,d), 20, 23, 25(a,c,e), 27(a,c,e), 30, 32.
1.4: 15 (odd), 7(a,f), 12(a), 13, 15

3 
Sep 7 
1.4, 3.1 
Read sections 1.4 and 3.1.
1.4: 15 (odd), 7(a,f), 12(a), 13, 15
3.1: 16, 811, 21

4 
Sep 21 
3.1, 11.1, 11.2 
Read sections 3.1, 11.1, and 11.2 up through definition 11.12.
3.1: Exercises
p.518: 2, 3, 5, 8, 10
p.528: 15

5 
Sep 28 
11.2 
Read the rest of section 11.2, starting after definition 11.12.
p.528: 914, 17

6 
Oct 5 
11.3 
Read section 11.3.
11.3: 17(odd), 811, 13, 15, 16, 18, 20, 21, 24, 30

7 
Oct 12 
11.4 
Read section 11.4 up through and including p. 548.
11.4: 3,5,6,8,10,18,19,21

8 
Oct 19 
Planar Coloring, 13.1 
Read section 13.1.
1. A graph is outerplanar if it can be drawn in the plane so that every vertex is on the outer face and no edge crosses another.
 (a) Let G be a graph and let H be the graph obtained from G by adding a new vertex adjacent to every other vertex. Prove that if G is outerplanar, then H is planar.
 (b) Find the maximum number of edges in an nvertex outerplanar graph without loops or multiple edges.
13.1: 2,3,5. Translation of 5 to English: Prove or disprove. For each vertex u in an edgeweighted graph, some shortest path from u to another vertex traverses at least one edge of minimum weight.

9 
Oct 26 
13.2, 13.3 
Read sections 13.2 and 13.3 up through and including Theorem 13.3 on p. 646647.
13.2: 1,2,3,4,5(a)
13.3: 1

10 
Nov 2 
13.3, 13.4 
Read sections 13.3 from Theorem 13.3 on p. 646647 and section 13.4.
13.3: 3,6,7
13.4: 2,3,4,7 (Hint for #7: Corollary 13.6)

11 
Nov 9 
13.4, Stable Matchings 
Read section 13.4; review class notes on Stable Matchings and the GaleShapley Algorithm.
13.4: 2,3,4,7 (Hint for #7: Corollary 13.6)
Stable Matchings: Five men (1,2,3,4,5) and five women (a,b,c,d,e) have the following preference lists:
1: baced 
a: 13542 
2: abecd 
b: 42351 
3: bcade 
c: 41325 
4: abdce 
d: 32154 
5: adecb 
e: 14532 
 Find the stable matching that results when the men propose.
 Find the stable matching that results when the women propose.
 Which couples, if any, are matched in every stable matching?

12 
Nov 16 
16.1, 16.5 
Read sections 16.1 and 16.5.
16.1: 1(ad,f),3,4,5
16.5: 1,2,3

13 
Nov 30 
16.6 
Read section 16.6.
16.6, p. 772: 14,5(a,b,c)

14 
Dec 7 
16.7 
Read section 16.7.
16.7, p. 772: 6a(iiv), 7, 8
