Introduction to Graph Theory 

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:  WEB PAGE

Basic Definitions


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.


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


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


Your grade will be based on your exam scores, homework grades and presentations according to the following percentages.

midterm exams 

25 % 


30 % 


25 % 


20 %

I will be happy to talk to you outside of the class during my office hours about any aspect of this class so feel free to drop by my office during office hours. If you have an academic conflict with my office hours, we can always set up an alternative meeting time. I hope you enjoy the course.

Homework Assignments



Due Date



2.7, 3.1, 3.2, 3.3






3.13, 3.14, 3.15(1)



3.15(2), 3.16, 3.17



3.22, 3.23, 3.26



4.7, 4.8, 4.9



5.2, 5.3, 5.4



6.1, 6.2, 6.3



7.1, 7.2, 8.1