Graph Theory (SP21)
Graph Theory, Math 38
***Please, fill out this survey. That will help me know your needs.***
Instructor: Nadia Lafrenière (nadia.lafreniere@dartmouth.edu). Pronouns: She/Her. I go by my first name.
Class schedule: Pre-recorded lectures (see the Panopto tab). Meetings on MW 1:10 - 2:15 PM, on Zoom, as well as Friday, May 28. Meeting ID: 988 5820 2512 (passcode: 673100). You must log in with your Dartmouth account.
x-hour: Tu 1:40-2:30 PM, will likely not be used
Office hours: Friday, 1:10-2:15 (during class time, no scheduled meeting), Tu 4-5 PM, or upon appointment, in the same Zoom meeting room.
Course description
Graphs are used to model pairwise relations between objects, using vertices and edges. The first result in graph theory dates back to 1736, when Euler answered the problem of the seven Bridges of Königsberg. Nowadays graphs are used to model such diverse things as social networks, traffic patterns, and map colorings.
This course will cover the fundamental concepts of graph theory: simple graphs, digraphs, Eulerian and Hamiltonian graphs, trees, matchings, networks, paths and cycles, graph colorings, and planar graphs. Famous problems in graph theory include: the Minimum Connector Problem (building roads at minimum cost), the Marriage Problem (matching men and women into compatible pairs), the Assignment Problem (filling jobs with applicants), the Network Flow Problem (maximizing flow in a network), the Committee Scheduling Problem (using the fewest time slots), the Four Color Problem (coloring maps with four colors so that adjacent regions have different colors), and the Traveling Salesman Problem (visiting a list of cities minimizing the traveled distance).
The class will be taught remotely. Here is how this applies to this course:
- The lectures will be presented in short pre-recorded videos that will be available for you to watch from anywhere. These will be posted on Canvas (see Panopto Video tab), and I hope to post them once a week, over the weekend.
- Since there are a lot of pre-recorded videos, Friday sessions will be used for drop-in office hours.
- The scheduled time for the class will consist in discussions about these videos, solutions to the homework problems for Wednesday's sessions, and complements of information. You are expected to attend these lectures if you can. If you can’t for reasons beyond your control (being a time zone that does not allow you to do so, need of taking care of relatives, low speed or no internet access, illness, etc.), please let me know in advance. These sessions will be recorded, but the goal is to make them as interactive as possible.
- Monday sessions will be for study groups. If a study group wants to meet at another time, they have to agree on a time and to let me know about this.
- You will be assigned study groups of 3-4 people. These are mandatory. As part of the evaluation, your contribution to study groups will be evaluated. I expect the study groups to meet through the course’s workspace on Slack or on Zoom. I will make the groups myself.
- There will be written assignments and quizzes, just as in a regular class. You are invited to discuss the problem sets with your study group. You can work with others as well on everything except the midterm exam.
Remote teaching & learning etiquette
Here are my expectations for our behavior towards others:
- Kindness and compassion is essential to respect others. Remember they can experience exceptional difficulties in these challenging times.
- I am still learning how to teach remotely, even after a year. Therefore, I am expecting you to give constructive feedback.
- Everyone’s participation is necessary for it to work. This is why I chose to form study groups, and why you are expected to attend remote sessions whenever you can. This will also provide you with very valuable social interactions.
- As a corollary of the previous, it is polite to turn on your camera whenever you can. It allows me to get some crucial feedback, and hopefully it allows others to know who you are.
- Do your best to be in a professional environment, even from home. That applies both for the way you dress, other things you could be tempted to do during the class and the background.
- During class time and when you watch the videos, I highly recommend you take notes just like you were in class. One reason for that is that writing what you understand makes memorizing it easier. Another reason is that it helps for locating the information when class is over.
Assessment
Here is how much I will consider every assignment towards the final grade:
| Evaluation | Date | Value |
| Homework (written) | Every Wednesday | 40% |
| Quizzes | Generally twice a week (Monday, Friday) | 5% |
| Study groups (participation) | Every Monday (or upon arrangement) | 8% |
| Study groups (evaluation of peers) | 3 times | 2% |
| Midterm (take-home) | Week 6 | 20% |
| Final project | June 7 | 25% |
Textbook
Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice-Hall.
The home page of the textbook can be found here. Unfortunately, the whole text is not available on that page, which is mostly for complements. You should purchase it, either from your local bookstore, or otherwise from an online provider.
Day-by-day Syllabus
|
|
Sections of the book |
Brief Description - Pre-recoded videos |
Brief Description - Class time |
|
Week 1 |
1.1 |
Day 1: Motivating example Day 2: Basic definitions, examples of problems in graph theory. Day 3: Adjacency and incidence matrices, isomorphisms. |
Day 1: Virtual tour of the class and tools, motivating example. Day 2: First examples of proofs. Day 3: Office hours |
|
Week 2 |
1.2, 1.3 |
Day 4: Paths, walks, cycles, components, cut-edges, cut-vertices, induced subgraphs. Day 5: Characterization of bipartite graphs, Eulerian graphs. Day 6: Vertex degrees, degree-sum formula, reconstruction conjecture. |
Day 4: Day 1 of study groups! Day 5: Arguments for counting Day 6: Office hours |
|
Week 3 |
1.3, 1.4 |
Day 7: Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph, triangle-free graphs, etc. Day 8: Degree sequences, graphic sequences, directed graphs. Day 9: Connected digraphs, Eulerian digraphs, De Bruijn cycles. |
Day 7: Study groups! Day 8: Questions on homework Day 9: Office hours |
|
Week 4 |
2.1, 2.2 |
Day 10: Orientations and tournaments. Trees and forests, characterizations of trees. Radius and diameter. Spanning trees. Day 11: Enumeration of trees, Cayley’s formula, Prüfer code. Day 12: Counting spanning trees, deletion-contraction. |
Day 10: Study groups! Day 11: Questions on homework Day 12: Office hours |
|
Week 5 |
2.3, 3.1 |
Day 13: The matrix tree theorem, graceful labelings. Day 14: Minimum spanning trees (Kruskal’s algorithm), shortest paths (Dijkstra’s algorithm). Day 15: Matchings, maximal and maximum matchings, M-augmenting paths. Hall's theorem and consequences. |
Day 13: Study groups! Day 14: Questions on homework Day 15: Office hours |
|
Week 6 |
3.1, 4.1 |
Day 16: Min-max theorems, maximum matchings and vertex covers, independent sets and edge covers. Midterm Due (we'll discuss the day). Day 17: Independent sets and edge covers (continued). Connectivity, vertex cuts. Day 18: Edge-connectivity, disconnecting sets, Whitney's theorem. |
Day 16: Study groups! Day 17: Questions on homework Day 18: Office hours |
|
Week 7 |
4.2, 4.3 |
Day 19: Blocks, k-connected graphs, Menger’s theorem. Day 20: Line graphs. Network flow problems, flows and source/sink cuts. Day 21: Ford-Fulkerson algorithm. Max-flow min-cut theorem. |
Day 19: Study groups! Day 20: Questions on homework Day 21: Office hours |
|
Week 8 |
5.1, 5.3 |
Day 22: Graph coloring. Day 23: Bounds on chromatic numbers, chromatic numbers of graphs constructed from smaller graphs. Day 24: The chromatic polynomial, the deletion-contraction recurrence. |
Day 22: Study groups! Day 23: Questions on homework Day 24: Office hours |
|
Week 9 |
5.3, Chapter 6 |
Day 25: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations. Day 26: Planar graphs, Euler's formula. Day 27: Kuratowski's theorem. |
Day 25: Study groups! Day 26: Questions on homework Day 27: Study groups! (since there is no class on Monday) |
|
Week 10 |
Chapter 6 |
Monday: No class, Memorial day. Day 28: Five and four color theorems. |
Monday: No class, no office hours. Memorial day. Day 28: Seven(!) color theorem. Last day of class |
|
Week 11 |
Final project |
Office hours by appointment. Final project due June 7. |
|
Consent to Record
(1) Consent to recording of course and group office hours
a) I affirm my understanding that this course and any associated group meetings involving students and the instructor, including but not limited to scheduled and ad hoc office hours and other consultations, may be recorded within any digital platform used to offer remote instruction for this course;
b) I further affirm that the instructor owns the copyright to their instructional materials, of which these recordings constitute a part, and distribution of any of these recordings in whole or in part without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including expulsion;
(2) Requirement of consent to one-on-one recordings
By enrolling in this course, I hereby affirm that I will not under any circumstance make a recording in any medium of any one-on-one meeting with the instructor without obtaining the prior written consent of all those participating, and I understand that if I violate this prohibition, I will be subject to discipline by Dartmouth up to and including expulsion, as well as any other civil or criminal penalties under applicable law.
Honor Principle
Assignments and examinations serve both the purpose of fixing your ideas on a given subject and, for the evaluator, to assess the comprehension you have of the class and how the class material has been understood. None of these goals can be achieved if you hand out a solution that is taken from someone else or from a publicly available source.
Nevertheless, students are allowed to work together on problems to explore their solutions. The homework you submit must reflect your own understanding, and you thus need to write your own copy of the solution, in your own words.
More information on the Academic Honor Principle can be found on Dartmouth’s website: https://students.dartmouth.edu/judicial-affairs/policy/academic-honor-principle
Student Accessibility and Accommodations
Students with disabilities who may need disability-related academic adjustments and services for this course are encouraged to see me privately as early in the term as possible. Students requiring disability-related academic adjustments and services must consult the Student Accessibility Services office by phone: 646-9900 or email: Stu-
dent.Accessibility.Services@Dartmouth.edu.
Once SAS has authorized services, students must show the originally signed SAS Services and Consent Form and/or a letter on SAS letterhead to me. As a first step, if you have questions about whether you qualify to receive academic adjustments and services, you should contact the SAS office. All inquiries and discussions will remain
confidential.
Mental Health
The academic environment at Dartmouth is challenging, our terms are intensive, and classes are not the only demanding part of your life. There are a number of resources available to you on campus to support your wellness, including your undergraduate dean (http://www.dartmouth.edu/~upperde/), Counseling and Human Development
(http://www.dartmouth.edu/~chd/), and the Student Wellness Center (http://www.dartmouth.edu/~healthed/). Remember, mental and physical health should be your number one priority!
Religious Observances
Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me as soon as possible, preferably before the end of the second week of the term to discuss appropriate accommodations.
Financial Needs
All material for this class is aimed to be freely available, either at the library or online. If you encounter financial challenges related to this class (because of the workload for example), please let me know.
Title IX
At Dartmouth, we value integrity, responsibility, and respect for the rights and interests of others, all central to our Principles of Community. We are dedicated to establishing and maintaining a safe and inclusive campus where all have equal access to the educational and employment opportunities Dartmouth offers. We strive to promote an environment of sexual respect, safety, and well-being. In its policies and standards, Dartmouth demonstrates unequivocally that sexual assault, gender-based harassment, domestic violence, dating violence, and stalking are not tolerated in our community.
The Sexual Respect Website (https://sexual-respect.dartmouth.edu) at Dartmouth provides a wealth of information on your rights with regard to sexual respect and resources that are available to all in our community.
Please note that, as a faculty member, I am obligated to share disclosures regarding conduct under Title IX with Dartmouth’s Title IX Coordinator. Confidential resources are also available, and include licensed medical or counseling professionals (e.g., a licensed psychologist), staff members of organizations recognized as rape crisis centers under state law (such as WISE), and ordained clergy (see https://dartgo.org/titleix_resources).
Should you have any questions, please feel free to contact Dartmouth’s Title IX Coordinator or the Deputy Title IX Coordinator for the Guarini School. Their contact information can be found on the sexual respect website at: https://sexual-respect.dartmouth.edu.