Math 725 (Graph Theory), Spring 2006

Essential Information

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

Problem Sets

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.

Final Project

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:

• Mon 4/3: Deadline for choosing an article
• Fri 5/5 - Wed 5/10: Presentations (to be scheduled)
• Wed 5/10: Due date for written report

Course Schedule

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