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 *P*_{4}'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.