| Week | Lecture dates | Sections | topics |
|---|---|---|---|
| 1 | 9/2 (Thurs) | 1.1-1.2 | Definitions and Degree |
| 2 | 9/8(W), 9/9(Th) | 1.3; 2.1-2.3 | Degree, Paths and distance |
| 3 | 9/13, 9/16 | 2.3-2.6 | Euler and Hamiltonian cycles, Travelling Salesman |
| 4 | 9/20, 9/23 | 3.1-3.3 | Connectivity and bridges |
| 5 | 9/27, 9/30 | 4.1-4.3 | Trees |
| 6 | 10/4, 10/7 | 5.1-5.5 | Vector spaces and graphs |
| 6 | 10/11, 10/14 | 1.1-5.5 | Review, Midterm |
| 7 | 10/18, 10/21 | 6.1-6.3 | Factorization and Matchings, Marriage Theorem |
| 8 | 10/25, 10/28 | 7.1-7.3 | Vertex colorings |
| 9 | 11/1, 11/4 | 7.4-5, 8.1-8.3 | Edge corings, Planar graphs |
| 10 | 11/8, 11/11 | 9.1-9.3 | Labelled graphs |
| 11 | 11/15, 11/18 | 11.1-11.3 | Oriented Graphs, Midterm |
| 12 | 11/22-26 | --- | No classes |
| 13 | 11/29, 12/2 | 12.1-12.3 | Critical Paths |
| 14 | 12/6, 12/9 | 13.1-13.5 | Network Flows |
| 15 | 12/13(M) | Review | |
| XX | 12/21(Tues) | Final Exam (8-11 AM) | |
| Due date | Homework Section/Problems |
|---|---|
| 12/13 | 13.2 #6(ii); 13.4 #3(2),6(i); 13.5 #2,4 |
| 12/6 | 11.2 #1(iii),6(i),11; 11.3 #1; 12.2 #1,3; 13.1 #2,5 |
| 11/15 | 8.3 #2; 9.2 #2,7,9 (edge-magic graphs) 9.1: Show that 7-cycles and 8-cycles are graceful. What about hexagons? |
| 11/8 | 7.4 #1,4,8; 8.1 #2,4; 8.2 #1(ii,iv),4 |
| 11/4 |
123456
Use the algorithm for Hall's Marriage Theorem to 654321 complete the 2x6 array at left into a 6x6 Latin square. |
| 11/1 | 7.1 #3,6,12; 6.2 #2,3 7.3 #1, 6(i,iii,v) |
| 10/25 | 6.1 #3,4; 6.2 #2; 6.3 #2,7;
Give a 3-regular graph with no perfect matching. |
| 10/11 | 5.2 #3; 5.3 #2; 5.4 #3 |
| 10/7 | 4.1 #1,7; 4.2 #8;
4.3 #4(i,ii,v),5 Carry out the algorithm of #4.3.5 on the graph in #4(v) |
| 9/30 | 3.1 #2,7(iii); 3.2 #2 3.3 #2,5
and: If G has no cycles, show that every edge of G is a bridge. |
| 9/23 | 2.3 #3(i); 2.4 #2,4(i); 2.5 #2,4(i,iii); 2.6 #3(ii) |
| 9/16 | 2.1 #6,11,12; 2.2 #3,5,7 |
| 9/9/09 | 1.1 #3,5; 1.2 #3,11; 1.3 #3,7 |
Syllabus in Catalogue: Colorability, connectedness, tournaments, eulerian and hamiltonian paths, orientability, and other topics from the theory of finite linear graphs, with an emphasis on applications chosen from social, biological, computer science, and physical problems.
Charles Weibel / Fall 2010