Graph Theory

• Text: Graph Theory (Graduate Texts in Mathematics) (Paperback)
• Author: Reinhard Diestel
• Publisher: Springer Verlag
• ISBN-10: 3540261834
• ISBN-13: 978-3540261834
• This entire book exists online at Hyperlinked PDF (please don't print it out using school printers!)

Look up your grades

Ask Thea

1. Install Mozilla from Page for obtaining the Mozilla browser
   It will also be necessary to install math fonts for this browser. Information on how to install these can be found on
   The MathML Fonts Page
   For linux users, the necessary fonts can be found in: mozilla-math.tar.gz (these should be installed in X windows).

Note: Other web pages for this course will not necessarily even show up in other browsers! Once you have installed Mozilla and the fonts, you can check your installation by viewing:

The MathML Start Page

Use this to check whether MathML is working properly on your web browser. Unfortunately, the Windows version of Mozilla seems to have a bug that will cause it to complain about missing fonts even though the fonts are there (and Mozilla is using them correctly).

Topics covered

1. Introduction:
   • Definitions
   • Paths, cycles, and trees
   • Hamilton Cycles and Euler Circuits
   • Planar graphs
   • Application of Euler Trails to Algebra
2. Electrical Networks
   • Graphs and Electrical Networks
   • Squaring the square
   • Vector spaces and Matrices associated with Graphs
3. Flows, Connectivity and Matching
   • Flows in directed graphs
   • Connectivity and Menger's Theorem
   • Matching
   • Tutte's 1-factor thneorem
   • Stable Matching
4. Extremal Problems
   • Paths and cycles
   • Complete subgraphs
   • Hamilton Paths and Cycles
   • The Structure of Graphs
   • Szemerédi's Regularity Lemma
   • Simple Applications of Szemerédi's Lemma
5. Coloring
   • Vertex coloring
   • Edge colring
   • Graphs on Surfaces
   • List coloring
   • Perfect graphs
6. Ramsey Theory
   • The Fundamental Ramsey Theorems
   • Canonical Ramsey Theorems
   • Ramsey Theorem for Graphs
   • Ramsey Theory for Integers

Homework

Links

• Graph Thing Home Page
• Free hyperlinked book on graph theory

Exam Schedule

1. Exam 1, Week 3:
2. Exam 2, Week 6:
3. Exam 3, Week 9:

Lecture Notes

Lecture notes folder