Welcome   Math 484   Math 485   Math 486   Math 555   Math 497G  

Graph Theory

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, Microsoft and Yahoo! in feeding you web information. Graph Theory can also help track down criminals. It plays a major role in the functioning of your Facebook account and can be used to help analyze Twitter relationships.

Fall 2012 Syllabus

Class Notes (Raw Source) -- A collection of notes (~160 pages) covering everything we will study in class. If  you  find a typo, please send me an e-mail so I can fix it. The notes should be used with a book. Graph Theory is a huge subject and they don't cover everything. Notes are released under a Creative Commons Share-and-Share-Alike License.

If you want to contact me by anonymous e-mail, follow this link.

You can access previous course assignments and syllabi here (I'll post the 2012 elements here in a little while).

If you’re thinking of taking Graph Theory with me, you are welcome to e-mail me and ask anything you like. I’ll also share past teaching evaluations if you want to know what past students thought of me.

I try to mix the theory, algorithms and applications of Graph Theory into the class. I treat this as an advanced math course. Therefore, you will be expected to do some proofs. By the end of this course you should, ideally, have a very good working knowledge of Basic Graph Theory results, some algebraic graph theory and applications (Page Rank and Eigenvector Centrality, tree growing algorithms, max-flow / min-cut theory and its relation to Linear Programming, matching and covering, and random graphs. We may cover other topics depending on time and interest.

Group work is encouraged on everything. All exams are open-book and open-notes.