This is a syllabus for a one-semester course (Math 312) at the University of Illinois using the first edition of this text. The course includes both math and computer science students, both undergraduates and graduate students, in varying proportions. I offer this syllabus as an aid to other instructors designing courses from this book.
Many students in this course see graph algorithms repeatedly in courses in computer science. Hence this course aims primarily to improve students' writing of proofs in discrete mathematics while learning about the structure of graphs. Some algorithms are presented along the way, and many of the proofs are constructive. The aspect of algorithms emphasized in CS courses is running time; the focus in a mathematics course in graph theory from this book is on proving that the algorithms work.
Math 312 is intended as a rigorous course that challenges students to think. Homework and tests should require proofs, and most of the exercises in the text do so. The material is interesting, accessible, and applicable; most students who stick with the course will give it a fair amount of time and thought.
In the exercises, problems designated by (-) are easier or shorter than most, often good for tests. Problems designated by (+) are harder than most. Those designated by (!) are particularly instructive, entertaining, or important.
Chapter 1 - Fundamental Concepts - 7 hours
Chapter 2 - Trees and Distance - 7 hours
Chapter 3 - Matchings and Factors - 5 hours
Chapter 4 - Connectivity and Paths - 6 hours
Chapter 5 - Graph Coloring - 5 hours
Chapter 6 - Edges and Cycles - 4 hours
Chapter 7 - Planar Graphs - 6 hours
Exams - 3 hours
Total - 43 hours
1.1.20-21; 1.2.14-15; 1.3.7; 2.2.12-14; 2.3.9-15; 2.4.4-5; 2.4.10-11; 2.4.16; 3.2.10; 3.2.14-16; 3.3.9-12; 4.1.19-20; 4.2.23; 4.3.13-16; 5.1.17; 5.2.10-11; 5.3.17-19; 6.1.8-11; 6.2.14-15; 6.3.all; 7.3.2; 7.3.11.
1.1.5-6; 1.2.16; 1.3.9; 1.4.8-9; 2.1.5; 2.1.10-14; 2.2.11; 2.2.19; 2.3.5-8; 3.2.11-13; 3.3.8; 4.1.4-5; 4.1.18; 4.2.21-22; 4.3.11; 5.3.8-9; 7.1.4; 7.1.21; 7.2.1-4; 7.2.8-12; 7.3.8-10.
Chapter 1. Undergraduates seem to appreciate the review of proof techniques in the first five sections; graduate students don't need it, so the emphasis on this can be adjusted to the mix of the class. To minimize confusion, it is better to ignore digraphs completely until the end of 1.4 (tournaments); students absorb the additional model more easily after becoming comfortable with the first. p2-5 contain motivational examples to be presented on the first day as an overview of the course; these definitions are later repeated where the concepts are studied in detail, so the second day can begin with 1.1.7 as long as bipartite graphs have been introduced. There is much benefit from fleshing out the intersection representation in 1.1.19.
The heaviness of the notation in 1.2.1 should be minimized; a path is a simple graph whose vertices can be placed in a linear order so that two vertices are adjacent if and only if they are consecutive in the order. 1.2.14-15 should be postponed until used.
1.3.7 is overly formal and can be skipped. Counting 5-cycles in the Petersen graph is worthwhile, but should be done by proving first that nonadjacent vertices have one common neighbor, which enables 5-cycles to be counted by counting P4's. Students benefit more from seeing 1.3.14 done by induction rather than by the pigeonhole principle; this will be rewritten.
Chapter 2. p67-68: Although most students in the class have seen determinants, most have considerable difficulty understanding the proof of the Matrix Tree Theorem; given the time involved, it is best merely to state the result and give an example. 2.2.12-14 should be skipped. p69-70: entertaining. p79-81: many students have seen rooted trees in computer science and find ordinary trees unnatural, so this may clarify the distinction. Many CS courses now cover the algorithms of Kruskal, Dijkstra, and Huffman; cover Kruskal, maybe cover Dijkstra, and skip Huffman. p87-98: Fleury's Algorithm is not worth the effort.
Chapter 3. p116-118: ``Stable Matchings'' is very popular when presented, but it is expendable to save time. p125-126: the material on f-factors is intellectually beautiful and leads to one proof of the Erdos-Gallai conditions, but it is not used again in the course and is an ``aside''. p127-130: matching algorithms in general graphs are important algorithmically but would require too much time in this course; this is ``recommended reading''.
Chapter 4. Bonds are dual to cycles in the matroidal sense; there are hints of this in exercises and in Chapter 7, but the duality cannot be fully explored until Chapter 8. Section 4.2 is one of the more difficult. p147-148: the proof of 4.2.9 is similar to that of 4.2.7, making it omittable, but the application in 4.2.13 is appealing. p149-152: The proof of Menger's Theorem changed between the first and second printing; students who still have the first printing should be given a copy of the proof using the Konig-Egervary Theorem.
p152-154: 4.2.20 can be skipped if neither of Exercises 4.2.20,23 is used, but these are worthwhile. CSDR (4.2.21-22) is an excellent but optional application of Menger's Theorem; it takes some effort. p166-169: The subsection entitled ``Supplies and Demands'' should be skipped, but 4.3.15 could be presented to illustrate application of integral feasible flows.
Chapter 5. p179: if time is short, the proof of 5.1.16 (Brooks' Theorem) can be merely sketched. p188-190: ``Forced Subdivisions'' is optional, but 5.2.9 should be presented if possible; the 3-connected case is done more simply using the Fan Lemma (or Menger's Theorem). 5.2.10-11 have limited appeal to undergraduates.
p196-197: Presentation of 5.3.8-9 requires conveying the idea of inclusion-exclusion. p199-200: if time is short, it suffices to state the equivalence of A and B in 5.3.13, without proving that B implies A. 5.3.15: It is probably best not to discuss perfection of line graphs of bipartite graphs at this point. 5.3.16: The perfection of chordal graphs can be proved using the chromatic polynomial, without induction.
Chapter 6. p212-214: it is appealing to give some structural understanding of line graphs by presenting 6.1.8 and stating 6.1.9 and 6.1.11, but the proofs are rather technical, and the entire subsection can be skipped. p220: skip the discussion of toughness; the conjecture that toughness 2 suffices is now known to be false. p232-246: skip or at least postpone until after Chapter 7.
Chapter 7. p248-250: if time is short, the Jordan Curve Theorem can simply be claimed; it may be better to present 7.1.5 first. p254: 7.1.15 is worthwhile, because the properties of outerplanar graphs make good exercises. p260-261: the preparatory material on Kuratowski's Theorem can be presented very lightly, leaving the annoying details as reading; the subsequent material on convex embedding of 3-connected graphs is much more interesting. p264-267: the algorithm makes an interesting example, but the proof is optional. p270-274: the four color problem is popular; for undergraduates, show the flaw in Kempe's proof (p271) but go no farther. p279: 7.3.8 can be sketched.
Chapter 8. If time permits, Section 6.3 or material from the first part of any section of Chapter 8 can be presented to give the students a glimpse of advanced material.