Math 412. Graph Theory
Instructor Syllabus
Text: Douglas B. West, Introduction to Graph Theory, 2nd Edition, Prentice-Hall, 2001.
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.
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 enjoyable, accessible, and applicable, so most students who stick with the course are willing to give it a fair amount of time and thought. Solutions for most exercises are available from the author.
Suggested Schedule
The subject matter for the course is the first seven chapters of the text, except for the optional Section 6.3, which should be postponed until after Chapter 7 if presented. Additional items are optional as discussed below (some of these could be stated without proof).
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 |
| Chapter 2 | Trees and Distance | 6 |
| Chapter 3 | Matchings and Factors | 5 |
| Chapter 4 | Connectivity and Paths | 5-6 |
| Chapter 5 | Graph Coloring | 5 |
| Chapter 6 | Edges and Cycles | 4 |
| Chapter 7 | Planar Graphs | 5-6 |
| * | Leeway and Exams | 6 |
| * | Total | 44 |
Items recommended to be skipped, unless time and instructor taste permits coverage: 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.18-19, 6.1.10, 6.2.14-15, 6.3.all, 7.3.2, 7.3.1 1.
Additional items that can be skipped when behind schedule: 1.2.16, 1.3.7-8, 1.4.9, 2.1.5, 2.1.10, 2.2.12-14, 2.3.4, 2.3.13-15, 2.4.4-5, 2.4.11, 3.2.11-13, 3.3.8, 4.1.4-5, 4.2.21-22, 4.3.11, 5.3.8-9, 5.3.17, 6.1.9-11, 7.1.21, 7.2.1-4, 7.2.8-12
Comments
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 issue can be adjusted to the mix of the class. 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. p17,19 contain the first of 13 figures that have dotted lines, which became almost invisible in the final printing.
Chapter 2. p67-68: most students in the class have seen determinants, so the proof of the Matrix Tree Theorem can at least be sketched; 2.2.12-14 are very optional. 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. Lower CS courses now seem to cover Huffman coding, so this becomes optional unless the class has many gad students. p88: in the figure, the errant label y should be a label x on the vertex in G'.
Chapter 3. p105: note the dotted lines. p116-118: "Stable Matchings" is very popular when presented. pl25-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 can be considered an "aside". pl27-130: matching algorithms in general graphs are important algorithmically but would require too much time in this course; call this "recommended reading".
Chapter 4. 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 easy application to 4.2.13 is appealing. pl49: treat the definitions for "path-multiplicity" lightly; they are provided only as a temporary name for l and l', which are then shown to equal k and k’. p150: dotted lines again. pl52-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 application of Menger's Theorem. The subsection entitled "Supplies and Demands" should probably 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 marked optional, but 5.2.9 should be presented if possible. 5.2.10-11 are rather nice but have limited appeal to undergraduates. p196-197: Presentation of 5.3.8-9 requires student familiarity with inclusion-exclusion. p199-200: if time is short, the proof of 5.3.13 can be merely sketched.
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 here are too technical for this course. p220: the discussion of toughness can be skipped, although the name generates amusement. p232-246: skip or at least postpone until after Chapter 7; this material win not be tested.
Chapter 7. p248-250: if time is short, the Jordan Curve Theorem can simply be claimed. p253: more dotted lines. p254: the properties of outerplanar graphs (7.1.15) are useful for 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 description of the algorithm makes an interesting example, but the proof is definitely optional. p270-274: the four color problem is popular, and it is reasonable to go as far as showing the flaw in Kempe's proof (p271); more than that is too technical for undergraduates. p275: more dotted lines! 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 other material.
Last modified June 17, 2002