# Introduction to Graph Theory  MTH548 - Fall 2003 Wed. 6:00 - 8:45, Tyler 106

## Instructor:  Dr. Nancy Eaton

E-mail me:  Phone:  874-4439
Office: Rm. 222, Tyler Hall
Office hours: Monday 1:30-3:00, Tuesday 10:30-12:00
Visit my web page:

FINAL EXAM

Notes

Announcement MTH 692 - Spring 2004

Homework Problems

Basic Definitons

## 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.
Topics include:

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 - Mathcings
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 Theor, D. West, Prentice Hall, ISBN: 0 13 014400 2

## Tests

There will be two exams 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 two exams will be given on Oct 15 and Nov 19. The final will be given on Friday, Dec 19 11:30-2:30, 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. Also, I will regularly ask class members to allow me to scan your solution to post on the web.  You will receive extra credit for this.

You will be asked toward the end of the semester to pick a section from one of our books that we have not covered and present it to the class.  Be sure to go over the presentation with me before presenting it to the class.