
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: 2686881 Office Hours: Tu 12:302, Fri 11:3012: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.
Midterms: There will be two outofclass midterms (held from 68pm 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, 68pm in Wean 7500 Midterm 2: Thursday,
April 2, 68pm in Wean 7500 Grading: Your course grade will be determined as follows:
Midterm 1: 20% Electronic devices: Calculators and other electronic devices will not be allowed during the exams, except to access the ebook for openbook 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 4122682922 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 selfharm, call someone immediately, day or night: CaPS: 4122682922 Re:solve Crisis Network: 8887968226 If the situation is life threatening, call the police: On campus: CMU Police: 4122682323 Off campus: 911 If you have questions about this or your coursework, please let me know. 
Return to Graph Theory Course Page
