Graph Theory (SP20)
Graph Theory, Math 38
***Please, fill out this survey. That will help me know your needs.***
Instructor: Nadia Lafrenière (nadia.lafreniere@dartmouth.edu)
Class schedule: Pre-recorded lectures. Meetings on MWF 12:50 - 1:55 PM, on Zoom. Meeting ID: 390-429-398
Pre-register here for the meeting: https://dartmouth.zoom.us/meeting/register/vp0tc-uhrTIijwTcZ6J0YBk3mqeg-A85kw
x-hour: Tu 1:20-2:10 PM, if necessary.
Website for the class: https://math.dartmouth.edu/~m38s20
Office hours: Th 4:30-5:30 PM, or upon appointment, in the same Zoom meeting room as for the live sessions.
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).
All classes offered by Dartmouth College for the Spring term 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, and I hope to post them 24 hours before the scheduled class.
- The scheduled time for the class will consist in discussions about these videos, and of solutions to the homework problems for Monday's and Wednesday's sessions. 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.
- Friday's 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 randomly 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.
- There will be assignments (written and webwork) and quizzes, just as in a regular class.
Remote teaching & learning etiquette
As it is most people’s first experience in a remote teaching context, and as these times can be stressful, I would like to describe 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 do not pretend to be an expert in remote teaching, so I am expecting you to give constructive feedback. I will certainly make mistakes, but the circumstances force the College to make a very fast transition to the remote setting.
- 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.
- 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 to 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
As all Dartmouth courses for this Spring term, your performance will be recorded as Credit or No Credit on your transcript. Outstanding performance will be acknowledged with the use of citations.
Circumstances in which you might receive the grade No Credit:
- Failure to submit assignments in a timely way;
- Failure to meet the criteria of the assignment;
- Failure to participate adequately in course activities
Here is how much I will consider every assignment:
| Evaluation | Date | Value |
| Homework (written or webwork) | Every week | 40% |
| Study groups (participation) | Every Friday (or upon arrangement) | 15% |
| Study groups (evaluation of peers) | 3 times | 5% |
| Midterm (take-home) | May 5 | 20% |
| Final exam (take-home) | June 3–9 | 20% |
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 |
Brief Description |
|
Week 1 |
1.1 |
Day 1: Virtual tour of the class and tools, motivating example. Day 2: Basic definitions, examples of problems in graph theory. Day 3: Adjacency and incidence matrices, isomorphisms. |
|
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. |
|
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. |
|
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. |
|
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. |
|
Week 6 |
3.1, 4.1 |
Day 16: Min-max theorems, maximum matchings and vertex covers, independent sets and edge covers. Midterm Due. Day 17: Independent sets and edge covers (continued). Connectivity, vertex cuts. Day 18: Edge-connectivity, disconnecting sets, Whitney's theorem. |
|
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. |
|
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. |
|
Week 9 |
5.3, Chapter 6 |
Monday: No class, Memorial day. Day 25: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations. Day 26: Planar graphs, Euler's formula. |
|
Week 10 |
Chapter 6 |
Day 27: Kuratowski's theorem. Day 28: Five and four color theorems. |
Final exam due June 7.
Honor principle, student accessibility, mental health and religious observances
Remember that Dartmouth's academic honor principle applies to this course.
Students requesting disability-related accommodations and services for this course are encouraged to schedule a phone/video meeting with me as early in the term as possible. This conversation will help to establish what supports are built into my online course. In order for accommodations to be authorized, students are required to consult with Student Accessibility Services (SAS; student.accessibility.services@dartmouth.edu; SAS website; 603-646-9900) and to email me their SAS accommodation form. We will then work together with SAS if accommodations need to be modified based on the online learning environment. If students have questions about whether they are eligible for accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.
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, Counseling and Human Development, and the Student Wellness Center. All these are open even this term.
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 before the end of the second week of the term to discuss appropriate accommodations.
Consent to record
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;
b) I authorize Dartmouth and anyone acting on behalf of Dartmouth to record my participation and appearance in any medium, and to use my name, likeness, and voice in connection with such recording; and
c) I authorize Dartmouth and anyone acting on behalf of Dartmouth to use, reproduce, or distribute such recording without restrictions or limitation for any educational purpose deemed appropriate by Dartmouth and anyone acting on behalf of Dartmouth.
Requirement of consent to 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 or group meeting with the instructor and/or students 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.