VIGRE2 Vertical Intergration of Research and Education Department of Mathematics, University of Utah

MATH 4800








Spring 2009 course

Topic: Graph Theory
Instructor: Will Malone
Catalog Number: MATH 4800-1
Credits: 3
Time: TTh, 2:00-3:20pm

Registering requires obtaining the class number from the instructor.

Color a map with n colors so that no two adjacent countries are colored the same. What is the least number n that works for any map?

If the cost to travel between any 2 national parks in the USA is known what is the cheapest way to visit all of the parks exactly once?

Take a standard chess board and place a knight on any square. Using only the knight's chess movements can it land on every square exactly once and end up where it started?

How many guards does it take to guard a single floor of a museum?

One common theme shared by all of these problems is that they can be translated into problems involving graphs. A graph consists of two sets {Vertices} and {Edges} where each edge has two endpoints lying in the set of vertices. In fact the first paper in graph theory, written by Leonhard Euler in 1736, showed that no solution to the Konigsberg Bridge Problem existed by utilizing such a translation.

Starting from a rigorous definition of a graph the class will explore foundational problems and ideas in graph theory like the isomorphism problem, telling when a graph is planer, colorings of graphs, and Ramsey numbers then move on to explore the connections between graph theory and other branches of mathematics.

Tuition Benefit:
The NSF VIGRE program provides a small tuition benefit for US students (US citizens, nationals, and permanent residents). Details will be provided once total enrollment has been determined.

Past Courses:
Fall 2006, Math Finance
Spring 2007, Fractals
Fall 2007, Metric Spaces, The Contraction Mapping Principle, Fractals & Other Applications
Spring 2008, Knot Theory
Fall 2008, Random Walk: Modeling, Theory, and Applications