Graph Theory: Lecture Notes

This is version two of set of lecture notes for MATH 485, Penn State's undergraduate Graph Theory course. Graph Theory is the study of discrete mathematical structures composed of vertices (nodes) represented by dots and edges (links) represented by lines connecting the dots. Generally speaking, Graph Theory is a branch of Combinatorics but it is closely connected to Applied Mathematics, Optimization Theory and Computer Science. In its applied form, Graph Theory is used every day by Google and Microsoft in feeding you web information. It plays a major role in the functioning of your Facebook account and can be used to help analyze Twitter relationships. Graph Theory can also help track down criminals and makes your GPS function.

The lecture notes are loosely based on Gross and Yellen's Graph Theory and Its Applications, Bollobas' Modern Graph Theory, Diestel's Graph Theory, Wolsey and Nemhauser's Integer and Combinatorial Optimization, Korte and Vygen's Combinatorial Optimization and several other books. All of the books mentioned are good books (some great) but I like different parts of each of them. Consequently I've combined 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 max flow 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.