640:428 Graph Theory,
Graph Theory for Fall 2007
- Text: Chartrand, G., and Zhang, P.,
Introduction to Graph Theory, McGraw-Hill, 2005.
- Syllabus Outline: We shall cover material from the
first ten chapters of the text plus additional material as time
allows. This includes: study of vertex degrees; graph isomorphism;
trees; vertex and edge connectivity of graphs and Menger's theorem;
Eulerian graphs and Hamiltonian graphs; digraphs and tournaments;
matching and factorization; planar graphs; graph coloring.
As part of the discussion of connectivity, we shall also discuss
network flow problems and the max flow-min cut theorem. Class notes
will be provided on these topics. Additional topics as time allows:
Turan's theorem and Ramsey numbers; distance and graph centers.
- Class Meetings: Monday and Thursday, 12:00-1:20, SEC
206, Busch Campus
- Reserve Reading: The following books are on reserve
at the SERC Undergraduate Reading room. No readings will be required
from these books, but they will occasionally be referred to in
lecture, and students might enjoy looking at them.
- Wilson, R. J., Introduction to Graph Theory ,
Fourth Edition, Longman, 1996.
- Gould, R., Graph Theory , Benjamin/Cummings, 1988.
Lecture by lecture syllabus and homework assignments:
This link is a lecture by lecture record of
topics covered, readings assigned, and problems assigned, and links
to additional material posted on the web. It will
be up-dated as the course progresses.
The instructor is Dan Ocone.
Office Hours: Wednesday, 2-3PM in Hill Center, Room 518.
Homework and Tests
The graded work for this course consists of assigned problems to
be handed in(100 points), two in-class midterm exams (100 points
and a final (200 points). Grades will be based on the sum total of
Homework is very important in this class. Problem
set will be assigned weekly, and students will be required
to hand selected problems in. Late homework is not accepted.
responsible for all problems assigned, not just the problems required
to be handed in. By doing the homework problems, students will learn
the concepts and techniques necessary for doing well on the exams.
Many problems in graph theory are of the form: "Prove ....." or
"Prove or disprove...". Your answer to such questions should be in the form of
a concise, yet clear, logical, and fully justified demonstration of the claim,
written in full English sentences. Writing up a good solution
can be hard work, even if you personally understand the idea
clearly. I expect you to treat these write-ups as short writing
exercises. You should always make a preliminary draft of the solution
and then write a neat, final draft. Students should
read the page on homework for
further advice and for the format in which problem solutions
should be submitted.
You may certainly work with other students in doing problems.
Putting heads together will help you come up with the idea behind
HOWEVER, once you see the solution,
you should write it up on your own.
Copying another's solution is considered to be academic dishonesty and
it does you no good as you don't learn the material.
You are welcome to use other sources--the web, another book, a -->
--classmate, etcetera--but you should cite them in your solution.
Exams are closed book. No calculators are allowed. You may
bring a single (two-sided) sheet of paper with whatever
material on it that you desire.