Graph theory is the study of, well, graphs.  Not in the y=f(x) sense, but in the discrete math/computer science vertices connected by edges sense.  Here’s a (directed) graph:

Here’s another one:

Ooh, pretty.  You’re on another graph right now -- the internet (think web pages are vertices, links are edges).  Graph theory began around 1736 when Euler addressed the Konigsberg bridge problem.  Here’s a picture:

The problem:  pick a place to start and, crossing every bridge exactly once, return to where you started.  Yeah, it’s hard.  Like, really really hard.  Like, you can’t do it hard.  “Why not?” is a question easily answered by graph theory.

From these humble beginnings graph theory has grown to an essential tool in analyzing networks of all types, with applications to computer science, coding theory, network security, optimization, and many many other areas.  It’s also a fertile area of undergraduate research, and the subject of many REUs.

This course will be a friendly introduction to many different areas of graph theory, both classical and new.  For more general info on graph theory check out this siteHere’s a recent article on another famous graph theory problem -- the four color problem.  For those of you in Disco, check out Chapters 11-13 of Dr. Grimaldi’s text.

Also feel free to email me with any questions.