Math 451/551: Graph Theory

Spring 2018


Important Links

Instructor and Meeting Times

Instructor: Nathan McNew
Office hours: Mondays and Wednesdays 11-11:50, Wednesdays 4:50--5:50 and by appointment
Office: 326 (2 × 163) 7800 York Road
Lecture: Tuesday and Thursday: 11:00--12:15 YR 129

Note that you do not need an appointment to attend regularly-scheduled office hours. If you have a conflict you may make an appointment to meet outside those times.

Course Description and Objectives

Course description:
Hamiltonian and Eulerian graphs, coloring graphs, planar and non-planar graphs, connectivity problems; isomorphic graphs, and advanced topics.

Course objectives: Students will learn the basics of graph theory, with a focus on problem solving techniques, proofs, and selected applications.

Prerequisites: MATH 263 or MATH 267.


A First Course in Graph Theory by Gary Chartrand and Ping Zhang. Other selected resources may also be posted here.


A number of problem sets will be posted on the homeworks tab of this page. Students will need to prepare written solutions for each of these problems, and these problems will be graded. These written solutions must be turned in before the corresponding class discussion of the solution for the solution to receive full credit.

Students will be asked to participate in class, by presenting solutions to homework problems and asking/answering questions.

Expect to spend a substantial amount of time studying, working on homework and preparing for the course. The general rule is two to three hours outside class for each hour inside; this translates to about 6-9 hours of homework and personal study per week.

Additionally, each student is responsible for writing up notes describing what was covered during one of the lectures during the term. These notes should be written up clearly using latex and submitted to the instructor within a week of the class period. Students are also encouraged to include additional examples/explanation. Notes will be posted for use by the rest of the class. Sign up for class periods here. Note: this will count as one homework assignment.

For graduate students enrolled in the Math 551 section, a final presentation will be required. You will need to meet with the instructor to select one of the Exploration sections from the textbook and give a 15-20 minute presentation on the material from that section in class.


There will be two midterm exams and a final exam covering the material presented in lectures, readings and on homework assignments.

Midterm 1 Midterm 2 Final Exam
Thursday, March 8th Thursday, April 26th Thursday, May 17th (10:15 AM)

If you have a conflict with a scheduled exam contact your instructor as soon as possible.


Grades will be assigned based on homework, in class presentations and participation, and labs and exams. They will be weighted in the students final grade as follows:

Component Math 451
Homework, and typed course notes 20%
Class participation/quizzes/presentation 10%
Midterms (Each) 20%
Final Exam 30%

Disabilities and Religious Observances

Any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities are encouraged to discuss appropriate accommodations with the instructor, either after class or during office hours.

Towson University is committed to providing equal access to its programs and services for students with disabilities, Students with disabilities should visit the Disabilities Services Web page, to learn about how to arrange for any appropriate accommodations. It is the student's responsibility to let the instructor know when he/she is a student with needs in this area. A memo from Disability Support Services (DSS) authorizing your accommodations will be needed.

If you have a religious observance that conflicts with your participation in the course, please meet with me before the end of the second week of the term to discuss appropriate accommodations.

Course Policies

Academic Integrity: This class is conducted in accordance with the Academic Integrity Policy. Cheating or plagiarism in any form is unacceptable. In particular:

On Exams: No assistance may be given or received except that you may ask the instructor for clarification of a problem. Calculators are not permitted.

On Homework: You are permitted and encouraged to collaborate with other students on the homework. However, after discussing the problems, you must write up the final solutions in your own words. You may use calculators and approved software. Additionally, you may consult your class notes and text. It is not permitted for someone to provide the answers for you. It is not permitted to submit answers found on the internet as your own work.

See this page from the MAA for information on how to avoid plagiarism in mathematical writing.

Class attendance is expected. If you miss a class, it is your responsibility to get the material and the homework assignment from your fellow students.

Diversity Statement: Towson University values diversity and fosters a climate that is grounded in respect and inclusion, enriches the educational experience of students, supports positive classroom and workplace environments, promotes excellence, and cultivates the intellectual and personal growth of the entire university community.

Last modified 24 April 2018.