Graph Theory (SP22)
Graph Theory, Math 38
Instructor: Nadia Lafrenière (Kemeny 318; nadia.lafreniere@dartmouth.edu). Pronouns: She/Her. I go by my first name.
Class schedule: 9L MWF 8:50-9:55 AM, in Haldeman 28
x-hour: 9Lx Th 9:05-9:55, will be used for study groups (mandatory)
Office hours: Monday and Wednesday, 2-3 PM, or upon appointment. My office is Kemeny 318
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).
Assessment
Here is how much I will consider every assignment towards the final grade:
| Evaluation | Date | Value |
| Homework (written) | Every Friday | 40% |
| Study groups (participation) | Every Thursday (x-hour) | 8% |
| Study groups (evaluation of peers) | 3 times | 2% |
| Midterm | April 28 | 20% |
| Final project (oral presentation) | May 27 & June 1 | 10% |
| Final project (written part) | June 6 | 20% |
Finding the right answer is not equivalent to solve a problem, and therefore your solution will be evaluated as a whole. Please, keep in mind while writing the assignments that I will not be with you when I will read it, so it must be complete.
The student presentations can be about any research paper in graph theory, or chosen in a list of topics that will be given to you by Early May, and that include coding projects as well as more theoretical projects. Students having further ideas should talk to me about the project they have.
The presentations and projects can be done in teams of two students, but the project should be bigger (longer talk and paper, or broader software project).
Extension policy
Every student is granted an automatic extension for one problem set; you however have to tell me before the submission deadline. This policy does not apply to the final project, midterm, nor to students talks, given that this would involve scheduling issues. I might grant extensions after the automatic one based on special circumstances, but students will need to ask for it.
Study groups
We will use the x-hour for study groups. During the first week of the term, you will be assigned a study group of 3-4 people. These are mandatory and serve as a way to improve the quality of the understanding of everyone: more experienced students might gain a lot of insight from explaining ideas to students who have not as much experience with proofs. As part of the evaluation, your contribution to study groups will be assessed. I expect the study groups to meet in the classroom, and I will make the groups myself to ensure a good balance.
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.
There is a copy of the textbook at the reserve desk of the Library (you can borrow the book for 4 hours at a time).
Day-by-day Syllabus
|
|
Sections of the book |
Brief Description - Course content |
|
1.1, 1.2 |
Day 1: Basic definitions, examples of problems in graph theory. Day 2: Adjacency and incidence matrices, isomorphisms. Day 3: Paths, walks, cycles, components, cut-edges, cut-vertices, induced subgraphs. |
|
|
1.2, 1.3 |
Day 4: Characterization of bipartite graphs, Eulerian graphs. Day 5: Vertex degrees, degree-sum formula, reconstruction conjecture. |
|
|
1.3, 1.4, 2.1, 2.2 |
Day 7: Degree sequences, graphic sequences. Day 8: Directed graphs, connected digraphs, Eulerian digraphs, De Bruijn cycles (pre-recorded video, no lecture; see announcement). Day 9: Trees and forests, characterizations of trees. Radius and diameter. Spanning trees (notes with blanks, complete notes) |
|
|
2.2 |
Day 10: Enumeration of trees, Cayley’s formula, Prüfer code. (notes with blanks, complete notes) Day 11: Counting spanning trees, deletion-contraction (notes with blanks, complete notes). Day 12: The matrix tree theorem, graceful labelings (notes with blanks, complete notes). End of the content for Midterm. Practice questions for the midterm |
|
|
2.3, 3.1 |
Day 13: Minimum spanning trees (Kruskal’s algorithm), shortest paths (Dijkstra’s algorithm). (notes with blanks, complete notes). Day 14: Matchings, maximal and maximum matchings, M-augmenting paths. Hall's theorem and consequences (notes with blanks, complete notes, Numberphile video). x-hour: Midterm (in-class) (exam, solutions) Day 15: Min-max theorems, maximum matchings and vertex covers, independent sets and edge covers (notes, supplemental proof) |
|
|
4.1, 4.2, 4.3 |
Day 16: Connectivity, vertex cuts, Edge-connectivity, disconnecting sets, Whitney's theorem (notes with blanks, complete notes) Day 17: Blocks, k-connected graphs, Menger’s theorem (notes with blanks, complete notes) Day 18: Line graphs. Network flow problems, flows and source/sink cuts (notes with blanks, complete notes) |
|
|
4.3, 5.1 |
Day 19: Ford-Fulkerson algorithm. Max-flow min-cut theorem (notes). Day 20: Graph coloring (notes with blanks, complete notes) Day 21: Bounds on chromatic numbers, chromatic numbers of graphs constructed from smaller graphs (notes with blanks, complete notes) |
|
|
5.3, 6.1 |
Day 22: The chromatic polynomial, the deletion-contraction recurrence (notes with blanks, complete notes). Day 23: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations. (notes with blanks, complete notes) Day 24: Planar graphs, Euler's formula. (notes) |
|
|
6.2, 6.3 |
Day 25: Kuratowski's theorem. (complete notes, notes with blanks) Day 26: Five and four color theorems. Seven(!) color theorem (notes). Day 27: Final project presentations |
|
|
Week 10 |
|
Monday: No class, Memorial day. Day 28: Final project presentations |
|
Week 11 |
Final project |
Office hours by appointment. Final project due June 6. |
Attendance and Health Policy
You are expected to attend class in person unless you have made alternative arrangements due to illness, medical reasons, or the need to isolate due to COVID-19. For the health and safety of our class community, please: do not attend class when you are sick, nor when you have been instructed by Student Health Services to stay home. My lectures notes are available on the course website, and I will provide the support you need to catch up on class material and submit your work. If needed, one-on-one office hours over Zoom will be offered.
Everyone is encouraged to wear a face mask during class, study groups and office hours. Even though this is not required (unless in specific circumstances - see the Face mask policy), I would prefer if you would wear a mask when you are physically close to me and during office hours. Please, be respectful of the preferences and comfort of others if they request you to wear a mask.
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. This includes, but is not limited to, the solution manual for the textbook.
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 requesting disability-related accommodations and services for this course are required to register with Student Accessibility Services (SAS; Apply for Services webpage; student.accessibility.services@dartmouth.edu; 1-603-646-9900) and to request that an accommodation email be sent to me in advance of the need for an accommodation. Then, students should schedule a follow-up meeting with me to determine relevant details such as what role SAS or its Testing Center may play in accommodation implementation. This process works best for everyone when completed as early in the quarter as possible. If students have questions about whether they are eligible for accommodations or have concerns about the implementation of their accommodations, they 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. Dartmouth has a deep commitment to support students’ religious observances and diverse faith practices.
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.