# MTH548 - Fall 2007 Wed. 3:30 - 4:45, Tyler 106

## Instructor:  Dr. Nancy Eaton

E-mail me:  Phone:  874-4439
Office: Rm. 208, Tyler Hall
Office hours: Wednesday 9:00-12:00 or by Apt.
Visit my web page:

The exercises.

HK assignments

List of All Theorems covered

## Course Content

Combinatorial Graphs serve as models for many problems in science, business, and industry.  In this course you will learn the basics about these structures.  You will see how theorems about graphs can be used to solve standard problems such as scheduling, network design, and routing.

Lesson 1 - Graphs Model Real World Problems
Lesson 2 - The Basics
Lesson 3 - Subgraphs and Isomorphisms
Lesson 4 - Paths and Cycles
Lesson 5 - Trees
Lesson 6 - Planar graphs
Lesson 7 - Independence and Coloring
Lesson 8 - Matching
Lesson 9 - Dominance
Lesson 10 - Connectivity
Lesson 11 - Network Flows

## Goals and Expectations

I expect you to learn the standard uses of graphs as models and the fundamental theory about graphs. This includes definitions, basic theorems, and being able to reproduce proofs of theorems. Also, as with any math course, you will improve your problem solving skills and both oral and written communication skills.

## Methods

I will present examples, definitions, theorems, and proofs in class. You should take careful notes and use this material as your study guide for exams.  We will not follow any particular book, but all of the material can be found in either of the two books that I am recommending that you obtain for the course and future reference.  The amount of detail given in the proofs in class will be greater than what you will find in either book.  Note also that there may be several correct, yet very different ways to prove a given theorem.
1.  Modern Graph Theory - Bela Bollobas, Springer-Verlag, ISBN: 0 387 98488-7
2.  Introduction to Graph Theory, D. West, Prentice Hall, ISBN: 0 13 014400 2

## Tests

There will be one midterm exam and a final. These tests will concentrate on the basic theorems and consequences thereof, which we have covered. You should learn the proofs of theorems that are presented in class. A list of theorems to be covered will be given before each exam. The midterm will be given on Oct 25.  The final will be given on Tuesday, Dec 18 3:00 pm, and will be comprehensive.

## Homework and Presentations

I will give out homework problems on worksheets during the semester. You should begin working on them as soon as you get them and hand them in when you have completed them. Due dates will be posted.  You will get comments from me on your homework and a grade of either 0, 1 or 2 for each problem. You will have an opportunity to hand in problems more than once, for a higher score.

You will be asked toward the end of the semester to pick a theorem that we have not covered and present it to the class, along with the necessary background material.  I will provide a list of theorems for you to choose from.

Upper bounds for Ramsey Number, R(s,t) T. Woodard

Turan’s Theorem C. Griep

Perfect Graphs A. Gerheim

Vizing’s Theorem D. Taylor

The Probabilistic Method A. Heissan

The Max Flow Min Cut Theorem S. Joseph

Mycielski’s Theorem G. Lugo