Homework: Homework is the most important part of this class. Doing lots of homework problems is crucial for doing well in this class. Some homework problems will help you learn the material and demonstrate this knowledge. Other problems will involve lots of experiments and open-ended investigation. The process of doing homework will help you find your own way of solving problems for the tests. Homework is due every Friday at the beginning of class. Late homework is only worth 50% of the total score. Homework must be neat, legible, and stapled in order to receive credit. I encourage you to brainstorm the problems in groups and write up your solutions independently. Remember to explain all your work.

HW1: due 8/29
READ: Section 1.1 Tucker
BOOK PROBLEMS: S1.1: pages 11-16, #4,9,25 (i and iii only),36
OTHER PROBLEMS: A) Fill out the "map of the U.S." worksheet.
B) Pick 5-10 graphs (from the book, or draw your own). Count the number of edges. Add up the degrees of all the vertices. How are these numbers related?
C) Remember that for a complete graph, there is an edge between every two vertices. How many edges are there for a complete graph in the case that the number v of vertices is 2,3,4, or 5? Can you find a formula that tells how many edges there will be when the number of vertices v is large?

HW 2: due 9/5
Read: Sections 1.2-1.3 Tucker
Book problems: S1.2: pages 21-25, #6(a-h), 14,16; S1.3: pages 30-32, #1,6,8a,12.
Other problems: A) Pick 5-10 planar graphs (from the book, or draw your own). Count the number of vertices, edges, and regions. (Don't forget the region outside the graph!) Find a formula that relates these numbers.

Quiz: in class on Wednesday 9/10, will cover Chapter 1 of Tucker.

HW 3: due 9/12
Read: Section 1.4 Tucker
Book problems: S1.4: #3(a-d, redraw the planar graphs without any edge crossings and highlight the K33 configuration in the nonplanar graphs),
7(abc), 12(ab), 17, 27(ac).
Other problems: Bring in a map of Africa (for example, there's one at http://www.heather-ellis.com/africa/MapTravelsAfrica.htm) which is colored with only 4 colors, so that no two adjacent countries have the same color.

HW 4: due 9/19
Read: Appendix 2 (pages 392-393) and Sections 2.1, 2.2 Tucker
Book problems: A2 (pages 393-395) #1, #21; S2.1: #2,9,10,16,19(a-c); S2.2: #4(c-f), 8(b), 11.
(hint for #10 in S2.1: for each square, how many others can the knight jump to?)

HW 5: due Friday 9/26
Read: Sections 2.3, 2.4, 3.1 Tucker
Book problems: S2.3: 1(g-i),6,7a,8; S2.4: 2,10; S3.1 1c, 2, 3, 10, 19, 23, 26.
Other problems: A) Construct a map by drawing a continuous curve which begins and ends at the same point and crosses itself as many times as you want. Determine how many colors are needed to color this map and explain why this is true in general.

HW 6: due 10/10
Read: Sections 3.2, 3.3, 4.1, 4.2 Tucker
Book problems: S3.2: 1c,2c,4, 5, 16a, 19; S3.3: 5,6,7b; S4.1: 3(a-c), 4; S4.2:1.

HW 7: due 10/17
Read: Sections 5.1, 5.2, 5.3 Tucker
Book problems: S5.1: 7,9,14,18,32; S5.2: 14,22,28,55; S5.3: 2,5,7,18.

HW 8: due 10/24
Read: Sections 5.4, 5.5, Appendix A4 (pages 399-402) Tucker
Book problems: S5.4: 4,8,10a,44; S5.5 1b, 2a, 4b, 14c; A4: 2,4,8.

HW 9: due 11/7
Read: Sections 6.1, 6.2, 6.3 Tucker
Book problems: S6.1: 2a, 4b, 14; S6.2: 12,19,20,27; S6.3: 1b, 2a, 4.

HW 10: due 11/14
Read: Sections 7.1, 7.3 Tucker
Book problems: S7.1: 2, 4, 15, 16a; S7.3: 3ab.
Other problems: show every fourth fibonacci number is divisible by 3.

HW11: due 11/21
Read: Sections 7.4, 7.5 Tucker
Book problems: S 7.1: 24; S7.3: 5, S7.4: 1c, 2, 6, 9c; S7.5: 1a, 2a.

HW12: due 12/5
Read: Sections 8.1,8.2 Tucker
Book problems: S8.1: 2,10,14,16,22; S8.2: 2,5,22; extra credit S8.3: 8a.

HW13 (last homework!): due 12/12
Other problems:
1. Find a 5-by-5 magic square.
2. Find two orthogonal 5-by-5 Latin squares and solve the officer's problem when n=5.
3. Draw a complete graph on 7 vertices and color its edges so that the edges with each color form a triangle.
How many trianges do you need?
4. A 6-by-6 chessboard is perfectly covered with 18 dominos.
Prove that it is possible to cut it either horizontally or vertically without cutting through a domino, in other words that it has a fault line.
Do either problem 5A or 5B
5A. Construct a perfect cover of an 8-by-8 board by dominos which has no fault line.
5B. Show how to cut a cube (3 feet on an edge) into 27 unit cubes (1 foot on an edge) using exactly 6 cuts,
but making a non-trivial arrangement of the pieces between two of the cuts.

Info on Final
The final covers Tucker Sections 1.1-1.4, 2.1-2.4, 3.1-3.2, 4.1-4.2, 5.1-5.5, 6.1-6.3,
7.1, 7.3-7.5, 8.1-8.2, A2, A4, and random topics from class.
At the moment, I expect the format of the final will consist of 10 short questions and 2 long questions,
but I'll update this by Monday after I've written it.
No books or notes are allowed. A calculator will not be necessary, but you can use one if you want.
If you think there is any formula or definition that you are in danger of forgetting, send me an e-mail.
If it seems reasonable, I will put these formulae either on the board or on the exam itself.