### Math 154 Spring 2022

#### Homework and Exam Dates

All homework assignments are turned in on Gradescope. The quizzes are submitted on Canvas. For more information on how to access and submit the quizzes, see the syllabus.

Week Monday Tuesday Wednesday Thursday Friday
1
Mar 28 Mar 29 Mar 30 Mar 31 Apr 1
2
Apr 4 Apr 5 Apr 6 Apr 7
Homework 1 due
11:59pm PDT
Apr 8
3
Apr 11 Apr 12 Apr 13 Apr 14
Homework 2 due
11:59pm PDT
Apr 15
Quiz 1 (on Canvas)
4
Apr 18 Apr 19 Apr 20 Apr 21
Homework 3 due
11:59pm PDT
Apr 22
5
Apr 25 Apr 26 Apr 27 Apr 28
Homework 4 due
11:59pm PDT
Apr 29
Quiz 2 (on Canvas)
6
May 2 May 3 May 4 May 5
No HW due
May 6
Midterm (in class)
7
May 9 May 10 May 11 May 12
Homework 5 due
11:59pm PDT
May 13
8
May 16 May 17 May 18 May 19
Homework 6 due
11:59pm PDT
May 20
9
May 23 May 24 May 25 May 26
Homework 7 due
11:59pm PDT
May 27
Quiz 3 (on Canvas)
10
May 30
No class
(Memorial Day)
May 31 Jun 1 Jun 2
Homework 8 due
11:59pm PDT
Jun 3
Finals
Jun 6 Jun 7 Jun 8 Jun 9 Jun 10
Final Exam
7-10pm PDT
Location: WLH 2001

#### Lecture schedule

Here is a tentative schedule of what will be covered in each lecture, together with the relevant section(s) of the book: Introduction to Graph Theory (Course Notes), by Professor Jacques Verstraete. I will fill in the schedule for the remaining lectures throughout the quarter (and update the schedule with any other changes). This is only a rough schedule, and there will likely be some give and take between lectures.

Week Date Topic Book Sections
1 3/28 Definition and basic properties of graphs (warm-up, example) 1,1. 1.4
3/30 Basic classes of graphs, and the Handshaking Lemma (warm-up) 1.3, 1.5, 1.6
4/1 Subgraphs, connected graphs, and walks 1.7, 2.1, 2.2
2 4/4 Eulerian graphs (vocab slide, Eulerian slide) 2.3, 2.5
4/6 Hamiltonian graphs (+ finish Eulerian graphs)
Example of Hierholzer's Algorithm)
2.5
4/8 Finish Hamiltonian graphs 2.5
3 4/11 Bridges and trees (bridges slide, trees slide) 3.1
4/13 Breadth-first search, depth-first search (slide 1, slide 2, slide 3) 3.1, 3.4
4/15 Characterizing bipartite graphs (warm-up) 3.2
4 4/18 Prim's and Kruskal's Algorithms (warm-up) 3.5
4/20 Dijkstra's Algorithm
(Prim slide, Dijkstra slide, Dijkstra proof, Dijkstra video)
3.6
4/22 Independent sets and covers (warm-up) 5.1
5 4/25 Hall's Theorem 5.2
4/27 Systems of distinct representatives 5.3
4/29 Intro to coloring, degenrate graphs (warm-up, vocab) 6.4
6 5/2 Brooks' Theorem, scheduling problems (warm-up) 6.3, 6.5
5/4 Midterm Review
5/6 Midterm
7 5/9 Konig's Theorem (warm-up, vocab, coloring slide) 6.1
5/11 Euler's formula (warm-up, vocab) 7.1
5/13 Coloring planar graphs (warm-up, slides) 7.3
8 5/16 Flows and Capacities (warm-up) 8.1, 8.2
5/18 Cuts (warm-up) 8.3
5/20 The Max-Flow Min-Cut Algorithm
(warm-up, Ford-Fulkerson Algorithm example)
8.4
9 5/23 Proof of Hall's Theorem using Max-Flow Min-Cut (warm-up) 8.5
5/25 Vertex and Edge Connectivity (warm-up) 4.6
5/27 Proof of Menger's Theorems
(warm-up, paths slide, notes on proof of Menger's Theorem)
8.6
10 5/30 No Class (Memorial Day)
6/1 Fun problems :)   (warm-up)
6/3
6/10 Final Exam (Friday of finals week, 7-10pm)