## Math 428, Section 1 Fall 2005

### Schedule

Week Date of Monday Topic / Section of book Homework Comments
1 Aug. 29 Introduction and definitions. Notes. All problems on pages 6 and 7 of Wilson, except 1.4. Due 9/8. Classes start on Sept. 1.
2 Sept. 5 More definitions and examples. Notes. page 14: 2.2, 2.3, 2.5, 2.8, 2.13(i); page 20: 3.3, 3.5, 3.6; Due 9/15. No class Monday (Labor Day).
3 Sept. 12 Finish definitions and examples. Paths and connectivity. Cut vertices and bridges. Notes. page 30: 5.2, 5.5, 5.6, 5.7, 5.9, 5.10; page 34: 6.3, 6.4; Due 9/22.
4 Sept. 19 Euler and Hamilton. page 34: 6.7; page 37: 7.3, 7.5, 7.9; page 41: 8.1, 8.2, 8.4, 8.5; Due 9/29.
5 Sept. 26 Shortest path problem. page 46: 9.3, 9.5, 9.8, 9.9, 9.10, 9.11; page 51: 10.1, 10.5; Due 10/6. Midterm Thursday.
6 Oct. 3 Trees. page 57: 11.1, 11.2, 11.3, 11.8, 11.9, 11.11; Due 10/13.
7 Oct. 10 Spanning trees. Prufer codes. page 64: 12.1, 12.2, 12.4, 12.5, 12.13; page 69: 13.1, 13.3, 13.4, 13.5, 13.6; Due 10/24. Changed due date of homework to the 24th. Homework now assigned on and due on Mondays.
8 Oct. 17 DFS/BFS. Planar graphs. Polyhedral graphs. None.
9 Oct. 24 Dual graphs. Infinite graphs. page 76: 15.2, 15.3, 15.5, 15.8, 15.10(i); page 80: 16.1, 16.4(i), 16.6; Due 10/31.
10 Oct. 31 Coloring. page 85: 17.2, 17.4, 17.6, 17.8, 17.10, 17.11(i); page 92: 19.1, 19.3 (give an example which is not a cycle), 19.4; Due 11/7.
11 Nov. 7 Chromatic polynomials. None. Midterm Monday.
12 Nov. 14 Directed graphs. page 99: 21.2, 21.4; page 104: 22.1, 22.3, 22.4, 22.5; page 108: 23.3, 23.4, 23.6, 23.7; Due 11/21.
13 Nov. 21 Markov chains. page 111: 24.1, 24.2, 24.3, 24.4(i)(ii); Due 11/28. Thanksgiving -- No class Thursday.
14 Nov. 28 Matchings. page 114: 25.1, 25.2, 25.3, 25.4, 25.5, 25.6(i);
15 Dec. 5 Network flows. Max-flow equals min-cut. page 126: 28.2, 28.5, 28.6; page 130: 29.1, 29.2, 29.3, 29.4, 29.5, 29.7(i);
16 Dec. 12 Questions/catch-up. None. Last class and last office hours are on Monday, 12/12. Final is Dec. 16 from 8-11 am. The location is SEC-206.