Graph Theory: Penn State Math 485 Lecture Notes

Christopher Griffin wrote:The lecture notes are loosely based on Gross and Yellen’s Graph Theory and It’s Applications, Bollobás’ Graph Theory, Diestel’s Graph Theory, Wolsey and Nemhauser’s Integer and Combinatorial Optimization, Korte and Vygen’s Combinatorial Optimization and several other books that are cited in these notes. All of the books mentioned are good books (some great). The problem is, they are either too complex for an introductory undergraduate course, have odd notation, do not focus enough on applications or focus too much on applications. 

This set of notes correct some of the problems I mention by presenting the material in a format for that can be used easily in an undergraduate mathematics class. Many of the proofs in this set of notes are adapted from the textbooks with some minor additions. One thing that is included in these notes is a treatment of graph duality theorems from the perspective linear optimization. This is not covered in most graph theory books, while graph theoretic principles are not covered in many linear or combinatorial optimization books. I should note, Bondy and Murty discuss Linear Programming in their book Graph Theory, but it is clear they are not experts in optimization and their treatment is somewhat non sequitur, which is a shame. The best book on the topic of combinatorial optimization is by far Korte and Vygen’s, who do cover linear programming in their latest edition. Note: Penn State has an expert in graph coloring problems, so there is no section on coloring in these notes, because I invited a guest lecturer who was the expert. I may add a section on graph coloring eventually.