640:428 Graph Theory,
Fall 2007

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.
    1. Wilson, R. J., Introduction to Graph Theory , Fourth Edition, Longman, 1996.
    2. 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.
E-mail: ocone-at-math-dot-rutgers-dot-edu.

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 each), and a final (200 points). Grades will be based on the sum total of points.

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. Students are 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 a solution. 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.