Course Outline: Graph Theory concerns the study of sets of vertices, some pairs of which are connected by edges. These objects, known as graphs, can be used to model many different situations. For example, given a set of cities and driving distances between certain pairs which have roads between them, there is a graph theory algorithm to find the shortest path between any given pair of cities. Similarly, we might want to find the shortest total amount of road necessary to build in order to make sure that it is possible to travel between any pair of cities.

Given a set of cell phone towers, some pairs of which can communicate with one another, we could determine its robustness by finding the smallest number of towers which, if disabled, will cause a disconnection in service.

There are many applications, but we will also study properties of graphs and prove theorems which don't seem to be of immediate consequence. We will do this because graphs are beautiful! We'll work through as many chapters of the textbook as possible in a brisk, yet reasonable, pace.

Class Meetings: We will meet in Posner 151 on Mondays, Wednesdays and Fridays from 10:30am to 11:20am.

Course Staff: Chloe Ireland, Alka Earathu, Max Aires and Andrew Chen will hold office hours and conceptual reviews on Tuesday evenings: Office Hours

Instructor: jmackey@andrew.cmu.edu

Office: Gates 4005

Phone: 268-6881

Office Hours: Tu 12:30-2, Fri 11:30-12:30 and by appointment.

Course Website:  www.math.cmu.edu/~jmackey/math484/gt.html

Help: In addition to class, recitation sessions, and office hours, individualized tutoring and other help options are also available through Academic Development.

Homework: Homework exercises are an essential part of the course. It is difficult to understand the material and do well on the exams without working through the homework problems in a thoughtful manner. Discussion of the homework with your peers is encouraged, but copying any part of another person's homework is not permitted. Please think about the problems posed, your strategies, and the validity of your logic and explanations.

Homework is to be submitted through Gradescope by 11pm on the due date. Homework that is submitted after the due date and time, but before the solutions are posted will receive half credit (with an asterisk to get full credit if the course grade is borderline). Homework and Exam regrade requests must be submitted within one week of the return date.

Text: Graph Theory, 5th edition, by Diestel. A lower-quality version is available for free at diestel-graph-theory.com, but I highly recommend the ebook or picking up a hardcopy.

Midterms: There will be two out-of-class midterms (held from 6-8pm in Wean 7500) and a cumulative final exam (scheduled by the Registrar). Class will not be held on the Wednesdays before the midterms (2/19 and 4/1).

The dates of the midterm exams are as follows:

Midterm 1: Thursday, February 20, 6-8pm in Wean 7500

Midterm 2: Thursday, April 2, 6-8pm in Wean 7500

Grading: Your course grade will be determined as follows:

Midterm 1: 20%
Midterm 2: 20%
Homework: 30%
Final Exam: 30%

Electronic devices: Calculators and other electronic devices will not be allowed during the exams, except to access the ebook for open-book portions of the exams.

Wellness: Take care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often helpful.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit their website at http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.

If you or someone you know is feeling suicidal or in danger of self-harm, call someone immediately, day or night:

CaPS: 412-268-2922

Re:solve Crisis Network: 888-796-8226

If the situation is life threatening, call the police:

On campus: CMU Police: 412-268-2323

Off campus: 911

If you have questions about this or your coursework, please let me know.