# Kevin Milans : Teaching : Fall 2012 Math375

Kevin Milans (milans@math.wvu.edu)
Office: Armstrong Hall 408H
Office Hours: M 2:30pm-4:00pm, W 2:30pm-3:30pm, F 10:00am-11:00am, and by appointment
Class Meetings: MWF 1:30pm-2:20pm in Hodges Hall 302

Home | Course Syllabus (PDF) | Homework

### Homework

Note: answers to many odd-numbered exercises are available in the back of the textbook.

No. Due Date Sections Assignment
1 Aug 24 1.1, 1.2
• Read the course syllabus and sections 1.1 and 1.2.
• An ice-cream shop has 7 flavors. John visits the ice-cream shop 3 days in a row, ordering one scoop of ice-cream each day.
• How many ways can John order ice-cream?
• How many ways can John order ice-cream if he orders the same flavor on the first and third days?
• How many ways can John order ice-cream if he orders different flavors on the first and third days?
• What is the relationship between your answers? Explain.
• 1.1 and 1.2: 1--7 (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, 7--13(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: 1--5 (odd), 7(a,f), 12(a), 13, 15
• 3 Sep 7 1.4, 3.1
• Read sections 1.4 and 3.1.
• 1.4: 1--5 (odd), 7(a,f), 12(a), 13, 15
• 3.1: 1--6, 8--11, 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: 1--5
• 5 Sep 28 11.2
• Read the rest of section 11.2, starting after definition 11.12.
• p.528: 9--14, 17
• 6 Oct 5 11.3
• Read section 11.3.
• 11.3: 1--7(odd), 8--11, 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 n-vertex 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 edge-weighted 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. 646-647.
• 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. 646-647 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 Gale--Shapley 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
1. Find the stable matching that results when the men propose.
2. Find the stable matching that results when the women propose.
3. 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(a-d,f),3,4,5
• 16.5: 1,2,3
• 13 Nov 30 16.6
• Read section 16.6.
• 16.6, p. 772: 1-4,5(a,b,c)
• 14 Dec 7 16.7
• Read section 16.7.
• 16.7, p. 772: 6a(i-iv), 7, 8

• milans@math.wvu.edu