Topics: Graph Theory
Math 591
Fall 2010
MWF 11:00–11:50
Oliver Hall-Physical Sciences 3003

Prerequisite: MATH 300 and MATH 310 (or the equivalent), or permission of an instructor. It is expected that you are thoroughly familiar with the material from these courses, including: elementary set theory, modular arithmetic, counting, direct proof, contrapositive proof, proof by contradiction, if-and-only-if proof, proof by induction (both regular and strong), existence proof, counterexamples, relations, equivalence relations, partitions, integers modulo n, functions, matrix multiplication, etc.

You will also need creativity, imagination, and a good work ethic.

Text: Introduction to Graph Theory, by Douglas West (Second edition)
(ISBN 0-13-014400-2)

Course web page:

Graph theory deals with the mathematical properties of structures formed by nodes and interconnecting lines. Although its origins are in recreational mathematics, it has important applications to computer science, cryptography, chemistry, biomathematics, game theory, signal processing and electrical engineering. Despite such "serious'' applications, it remains the least technical and most fun branch of mathematics.

This course is an introduction to graph theory at the graduate or advanced undergraduate level. It is team-taught by VCU professors who are actively involved in graph theory research. Following is a list of professors. Click on the links to obtain office hours and contact information.


Ghidewon Abay Asmerom Harris 4104a
Dan Cranston Harris 4109
Richard Hammack Harris 4105
Craig Larson Harris 4106

Each professor covers roughly one or two chapters in four weeks. Weekly reading assignments from these chapters are given. You should read the material before we discuss it in class, and again after we discuss it. Your grade is determined by homework assignments, a midterm, and a final exam. Details follow.

Homework: Each professor will assign, collect and grade homework problems related to the material that he covers. Homework will be collected each Friday, unless noted otherwise.

Midterm: There will be one closed-book midterm test on October 15. More information will be given in the weeks prior to the test.

Final Exam: The final exam covers only the material presented after the midterm. It is scheduled for Monday December 13, 8:0010:50 am.

The 10-point grading scale is used:
A: 90100
B: 8089
C: 7079
D: 6069
F: 059
Your final average will be computed as follows:

Homework: 36%
Midterm: 32%
Final Exam: 32%

Last day to withdraw
: November 5

Accommodations: Any student eligible for and needing academic adjustments or accommodations because of a disability should contact me within the first week of class. The VCU Disability Support Services web site is

VCU Honor System:  All VCU students are presumed upon enrollment to have acquainted themselves with and have an understanding of the Honor System. Therefore, it is a student's responsibility to ask course instructors to clarify expectations for each assignment in order to be in compliance with the Honor System. The 2007 - 8 VCU Honor System policy statement and purpose is located at

Classroom Conduct: Professional conduct will be expected at ALL TIMES and disruptive talking or behavior will NOT be allowed.  A description of the VCU Student Conduct in Instructional Settings Policy can be found at:

VCU Statement on Safety  You can sign up to receive VCU text messaging alerts (  Keep your information up-to-date. Know the safe evacuation route from each of your classrooms. Emergency evacuation routes are posted in on campus classrooms.  Listen for and follow instructions from VCU or other designated authorities. Know where to go for additional emergency information (  Know the emergency phone number for the VCU Police (828-1234). Report suspicious activities and objects. University Counseling Services: