MTH 248: Graph Theory

Overview

The official course description is: Paths, circuits, trees; bipartite graphs, matching problems; unicursal graphs, Hamiltonian circuits, factors; independent paths and sets; matrix representations; planar graphs; coloring problems.

Instructor

Arjun Krishnan

  • Lectures: TR 12.30 - 1.45pm Hylan 305
  • Office: Hylan 817
  • Office Hours: 2 - 3pm Thursdays and 11-12pm Fridays in my office, or by appointment.
  • E-mail: arjun.krishnan at rochester dot edu
  • Teaching Assistant (TA): TBA
  • TA Office Hours: TBA

Textbook

Mandatory:

Introduction to Graph Theory, Douglas B. West. You can also buy them second hand.

I do not recommend getting a pirated copy from libgen even if you cannot afford it. There are a few copies on reserve at Carlson Library.

This will be supplemented by material from the following books. Pdfs of whatever you need will be posted online.

Grading

In-class presentation 10%
Homework 30%
Midterm 30%
Project 30%

Guaranteed grades: if you make these scores, then you are guaranteed a letter grade in the following ranges.

Grade Cutoff
A 90
B 80
C 70

I sometimes “curve up” linearly to help students with lower scores.

Homework

  • Will be assigned every week on this webpage on Tuesday after class.
  • You may choose to work with one other person. If you do, you must write both names on it, and receive the same grade.
  • Homework will be due on Tuesdays on gradescope.
  • Lowest score will be dropped.
  • You are encouraged to seek my help (or the TAs) either over email or during office hours.
  • Every Tuesday, we will start the class with a homework presentation. I will pick someone and a problem at random, and you will present your solution in class. This will count towards your participation grade. There are no rules for this, lady luck will determine who is selected.
  • I will grade one randomly selected problem a week.
  • Homework can be found here

Exams

Midterm: In class, Apr 17.

Final: Presentation based. See final projects

Academic honesty

All assignments and activities associated with this course must be performed in accordance with the University of Rochester’s Academic Honesty Policy. More information is available at: www.rochester.edu/college/honesty. This resource is great, and has a great FAQ section. There are some fairly scary policies. For example, if you’re found cheating, the instructor is required to report you. I intend to follow this policy.

In this class, there are separate collaboration policies for HW and exams. In short, you may collaborate on HW, but you must state it. You may not collaborate on quizzes.

Any usage whatsoever of online solution sets or paid online resources (chegg.com, chatGPT or similar) is considered an academic honesty violation and will be reported to the Board on Academic Honesty. In particular, any assignment found to contain content which originated from such sources is subject to a minimum penalty of zero on the assignment and a full letter grade reduction at the end of the semester (e.g. a B would be reduced to a C). This applies even if the unauthorized content was obtained through indirect means (through a friend for instance) and/or the student is seemingly unaware that the content originated from such sources. If you have any questions about whether resources are acceptable, please check with your instructor.

Help

If you are having difficulty seek help immediately - do not wait until it is too late to recover from falling behind. There are several avenues for you to get help and ask questions, outside of lecture:

Disability Support

The University of Rochester respects and welcomes students of all backgrounds and abilities. In the event you encounter any barrier(s) to full participation in this course due to the impact of disability, please contact the Office of Disability Resources. The access coordinators in the Office of Disability Resources can meet with you to discuss the barriers you are experiencing and explain the eligibility process for establishing academic accommodations. You can reach the Office of Disability Resources at: (585)275-9049; 1-154 Dewey Hall. Or, visit Center for Excellence in Teaching and Learning.

To be granted alternate testing accommodations, you must fill out forms with CETL at least seven days before each and every exam. These forms are not sent automatically.

Credit Hour Policy

This course follows the College credit hour policy for four-credit courses. This course meets 3 academic hours per week. Students are also expected to deepen their understanding of the course material through close examination/evaluation of the readings assigned in the course.