Introduction to Graph
Theory
MTH548  Fall 2007

Email
me: mailto:eaton@math.uri.edu 
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
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, SpringerVerlag, ISBN: 0 387 984887
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.
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.
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 % 
homework 
30 % 
final 
25 % 
presentation 
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.
Number 
Due Date 
Exercises 
1 
9/18 
2.7, 3.1, 3.2, 3.3 
2 
9/20 
3.5 
3 
9/27 
3.13, 3.14, 3.15(1) 
4 
10/4 
3.15(2), 3.16, 3.17 
5 
10/11 
3.22, 3.23, 3.26 
6 
10/18 
4.7, 4.8, 4.9 
7 
10/30 
5.2, 5.3, 5.4 
8 
11/1 
6.1, 6.2, 6.3 
9 
12/6 
7.1, 7.2, 8.1 