Office: 541 Snow Hall
Office hours: Monday 3:00--5:00 PM, or by appointment
Essential Information | Problem Sets | Final Project | Schedule | Links
Syllabus (PDF)
Lectures: MWF 12:00--12:50 PM, 301 Snow Hall
Instructor: Jeremy Martin
Office: 541 Snow Hall
Office hours: Monday 3:00--5:00 PM, or by appointment
KU course line number: 68132
Textbook: Douglas B. West, Introduction to Graph Theory, 2nd edition (Prentice-Hall, 2001). Available at KU Bookstore.
Midterm exam: Friday, March 10, in class
Problems |
Solutions
Final exam: Friday, May 19, 10:30 AM--1:00 PM, 301 Snow Hall
I'll post problem sets here every week or two. You'll always have at least a week between assignment and due date.
The assignments will be posted as PDF files; you may need Acrobat Reader to read them.
Each student will read a journal article on a topic in graph theory, write a short report (approximately 3--4 pages) summarizing its results, and give a short presentation (approximately 15--20 minutes) in class.
The details:
Important dates:
Please note that all information for future lectures is subject to change.
| Date | Textbook Sections | Topics |
|---|---|---|
| Fri 1/20 | 1.1 | Introduction |
| Mon 1/23 | 1.1 | Isomorphisms; adjacency and incidence matrices; Pn, Cn, Kn and Kn,m |
| Wed 1/25 | 1.2 | Subgraphs; the Petersen graph; girth; walks, trails and paths |
| Fri 1/27 | 1.2 | Connectedness, deletion, induced subgraphs |
| Mon 1/30 | 1.2, 1.4 | Bipartite graphs |
| Wed 2/1 | 1.3, 1.4 | Eulerian (di)graphs; handshaking |
| Fri 2/3 | 1.3 | Enumerative problems; hypercubes |
| Mon 2/6 | 1.3 | Extremal problems |
| Wed 2/8 | 2.1 | Characterization of trees |
| Fri 2/10 | 2.1 | More tree basics; exchange lemmas |
| Mon 2/13 | 2.3 | Kruskal's algorithm |
| Wed 2/15 | 2.2 | The Prüfer code |
| Fri 2/17 | 2.2 | Deletion-contraction |
| Mon 2/20 | 2.2 | The Matrix-Tree Theorem |
| Wed 2/22 | 2.2; 2.1 | Matrix-Tree examples; distance basics |
| Fri 2/24 | 2.3 | Dijkstra's algorithm |
| Mon 2/27 | 3.1 | Matchings; Berge's augmenting path criterion |
| Wed 3/1 | 3.1 | Hall's Marriage Theorem; vertex and edge covers |
| Fri 3/3 | 3.1 | The König-Egerváry and Gallai Theorems |
| Mon 3/6 | 3.2 | The Augmenting Path Algorithm (lecture notes) |
| Wed 3/8 | 3.2 | Weighted bipartite matchings and the Hungarian Algorithm |
| Fri 3/10 | MIDTERM EXAM | |
| Mon 3/13 | Class cancelled due to weather | |
| Wed 3/15 | 3.3 | Tutte's 1-factor theorem (lecture notes) |
| Fri 3/17 | 3.2 | Stable matchings |
| Mon 3/20 | No class - Spring Break | |
| Wed 3/22 | ||
| Fri 3/24 | ||
| Mon 3/27 | 4.1 | Connectivity and edge-connectivity |
| Wed 3/29 | 4.1 | The κ ≤ κ' ≤ δ theorem |
| Fri 3/31 | 4.2 | Bonds and blocks |
| Mon 4/3 | 4.2 | Whitney's theorems on 2-connectivity and 2-edge-connectivity |
| Wed 4/5 | 4.3 | Local connectivity and Menger's theorems |
| Fri 4/7 | 4.3 | Network flows I |
| Mon 4/10 | 4.3 | Network flows II |
| Wed 4/12 | 5.1 | Network flows III |
| Fri 4/14 | 5.1 | Coloring basics |
| Mon 4/17 | 5.3 | Brooks' Theorem; the chromatic function |
| Wed 4/19 | 5.3 | Chromatic recurrence; chordal graphs; acyclic orientations |
| Fri 4/21 | The Tutte polynomial I (lecture notes, updated 4/26/06) | |
| Mon 4/24 | The Tutte polynomial II | |
| Wed 4/26 | 6.1 | Planar graphs and planar duals |
| Fri 4/28 | 6.1 | Euler's formula |
| Mon 5/1 | 6.2 | The 5-color theorem (lecture notes) |
| Wed 5/3 | 6.2 | Kuratowski's theorem; embeddings of higher genus (lecture notes) |
| Fri 5/5 | Student presentations | |
| Mon 5/8 | Student presentations | |
| Wed 5/10 | Student presentations |