Math 154 (Spring 2025)
Summary
Math 154 is a first course in graph theory. We approach the subject from a pure, proof-based mathematics perspective, emphasizing theorems and their proofs rather than algorithms. However, we will try to emphasize the similarities with other approaches.
We will cover some approximation of the following topics:—
- Basic notions of graphs, trees, subgraphs, isomorphism, bipartite graphs, connectedness.
- Paths and cycles; Euler and Hamilton cycles.
- Matchings; Hall's theorem and Kőnig's theorem.
- Connectivity and k-connectedness.
- Graph colorings.
- If time: planar graphs, Kurotowski's theorem, the 4-color theorm.
Contacts
The instructor is Freddie Manners (email fmanners); my office is AP&M 7343. There are two TAs: Jasper Liu (email mol008) and Tristan Shin (email trshin).
Class and section
Lectures are held on Mondays, Wednesdays and Fridays, 0900–0950. They will be held in-person in Peter 103. The course will not be generally available as a podcast, and lecture attendance is mandatory. I will take lecture attendance, and some portion of your grade is assigned to class attendance.
Section is held in-person, on Wednesdays, either at 1700–1750 in CENTER 203 (Section A01) or 1500–1550 in PODEM 1A22 (Section A03). Section attendance is very strongly encouraged and attendance will be taken. Some course grade is tied to attend section at least once and office hours (with either TA or the instructor) at least once over the quarter.
Note there is NO class on Friday May 23 or on Monday May 26 (Memorial Day).
Exams
There will be two evening midterm exams, on Tuesday April 22 (Week 4) and Tuesday May 13 (Week 7), 2000–2130 (i.e., 8pm to 9:30pm), in CENTER 105. Sorry about the time.
The final exam is on Wednesday June 11, at 0800–1100. It is also in-person, in PETER 103. Sorry about the time.
You should ensure at the start of the quarter that you can attend these exams. In general, alternative modalities, dates or times (in particular, remote exams) will not be offered.
(Note: it is standard practice in the Mathematics Department to use multiple versions of exams where necessary.)
Exams will be closed-book. Use of any outside resources or communication in exams is, of course, strictly forbidden.
Homework
Homework is due every Saturday at 23:59 (11:59pm), starting in Week 1 (April 5). Deadlines may change as circumstances require.
You may collaborate in discussing and thinking about homework problems; indeed this is often beneficial. However, if you do, you must list your collaborators on your assignment when you turn it in. Moreover, you must not simply show another student a written solution to a problem, and when you write your own solutions, you \textbf{must do so alone and in your own words}, without looking at another solution. You may use outside resources, including the internet, other textbooks or AI tools, to help you understand the subject material. However, you may not attempt to find a solution to a specific homework problem using such resources. In particular, you may not post any homework problem as a question on the internet, or to an AI system.
It is guaranteed that every exam will contain at least one problem which is a close variant of a homework problem.
Your lowest homework grade for the quarter will be dropped, to allow for disruptions that may arise. Beyond this, I will not grant extensions or accept late homework, unless there are truly exceptional circumstances. Good-faith technical or logistical issues in turning in your homework (which result in very short delays) may be forgiven, on a case-by-case basis.
Grading
Your combined grade for the course is calculated as follows. First, you worst homework grade will be dropped. Then, take
- 20% homework;
- 20% midterm 1;
- 20% midterm 2;
- 35% final exam;
- 4% class attendance (capped at 80% attendance rate, then 0.05% grade for every 1% attendance below that);
- 1% for both attending section at least once, and attending office hours at least once.
The requirement to attend office hours at least once is intended to be fun and encourage dialogue. You don't have to have a specific question – it's ok to show up and chat in general terms.
The letter grade cut-offs will be at least as generous as the table below. However, I ultimately choose grade boundaries based on how well I think students have performed rather than by fixed values. In practice, because I tend to set somewhat difficult exams, the cut-offs are almost always more generous than the table, and occasionally much more generous.
| A+ | A | A- | B+ | B | B- | C+ | C | C- | F |
|---|---|---|---|---|---|---|---|---|---|
| 97 | 93 | 90 | 87 | 83 | 80 | 77 | 73 | 70 | < 70 |
Resources
In addition to this website, the course has a Canvas page, a Gradescope page and a Piazza site. The sign-up codes for Gradescope and Piazza are listed on the Canvas home page.
Provisional schedule
A very rough provisional course schedule is given below. It can and probably will change.
| Week | Mon | Wed | Fri | Topic |
|---|---|---|---|---|
| 1 | L1 | L2 | L3 | Introduction. Fundamental definitions af graph theory. |
| 2 | L4 | L5 | L6 | Mantel's theorem. Paths, cycles and connectivity. |
| 3 | L7 | L8 | L9 | Trees. Eulerian and Hamiltonian cycles. |
| 4 | L10 | Review | L11 | More cycles. Matching theory |
| 5 | L12 | L13 | L14 | More on matchings. Hall's and Kőnig's theorems. Applications. |
| 6 | L15 | L16 | L17 | Connectivity. Menger's theorem. |
| 7 | L18 | Review | L19 | Graph colorings. Vertex and edge colorings. |
| 8 | L20 | L21 | X | More on colorings. Brooks' theorem and Vizing's theorm. |
| 9 | X | L22 | L23 | Planar graphs. The four-color theorem. |
| 10 | L24 | L25 | Review | Further topics, if time. |
Office hours
Regular office hours and locations are listed in the table below. However, please check the calendar below for any one-off changes or cancellations.
| Instructor / TA | Location | Regular hours |
|---|---|---|
| Freddie Manners | APM-7343 | Wednesdays 12:30-1:30pm, Fridays 3:30-4:30pm |
| Jasper Liu | HSS 4070 | Fridays 2-3pm |
| Tristan Shin | HSS 4012 | Thursdays 3:30-4:30pm |
Course calendar
A link to add this calendar is available on the course's Canvas page.