Week 1 
Jan 6 
Syllabus
Introduction to Graph Theory
(slides 121)

Chapter 1 (1.1, 1.31.6) and Appendices A.2A.3

Ch. 1.2 is optional; it's an overview of topics in the book.

Jan. 8 

Jan. 10 

slides continued (rest of slides)
Subgraphs, walks, Eulerian and Hamlitonian graphs
(slides 117)

Chapters 1.7 and 2 (2.12.6; skip 2.7)

Week 2 
Jan. 13 

Jan. 15 

Jan. 17 

slides continued (rest of slides)

Week 3 
Jan. 20 
Martin Luther King, Jr. Holiday

Jan. 22 
Trees
(slides)
Spanning tree algorithms
(slides 13),
(worksheets)

Chapter 3.23.4

Please print out the worksheets at full size to facilitate note taking in lecture.

Jan. 24 

slides continued (451) + worksheets

The DFS example on the slides has a mistake, so I used worksheets on the projector instead. There were also several other examples on the worksheets on the projector. See the 1/24 and 1/27 podcasts to review it.

Week 4 
Jan. 27 

slides continued (rest of slides and worksheets)
Weighted graph algorithms
(slides 114)

Jan. 29 

Jan. 31 

slides continued (rest of slides)
Connectivity

Will be on the chalkboard, not on slides.

Chapter 4.44.5 and 4.7.
Skip other parts of Chapter 4 for now (may do later in the quarter if time permits).

Campuswide deadline to drop without a "W"

Week 5 
Feb. 3 

Chapter 4 continued

Example for question asked in class about a graph with λ(G)<δ(G), namely, 1<2:
(drawing)
Matchings

Chapter 5 intro to matchings (on chalkboard)

Feb. 5 

Chapter 5.1: Independent sets, matchings, vertex and edge covers

Feb. 7 
Midterm

Week 6 
Feb. 10 
Matchings: Hall's Theorem, applications, and generalizations
(slides 124)
[slides revised 2/10 after class]

Feb. 12 

slides continued (2539, 5761)

Feb. 14 

slides continued (rest of slides)

Campuswide deadline to drop with a "W"

Week 7 
Feb. 17 
Presidents' Day Holiday

Feb. 19 
Vertex and Edge Colorings
(revised slides 124, 4548)
[slides revised again 2/23]

Feb. 21 

Week 8 
Feb. 24 
Planar Graphs
(slides 116)

Chapter 7

Covering 7.17.3 in full, and parts of 7.4 and 7.67.8. Skipping 7.5.

Feb. 26 

Feb. 28 

slides continued (rest of slides)

Week 9 
Mar. 2 
The MaxFlow MinCut Theorem
(slides 131)

Mar. 4 

Mar. 6 

slides continued (rest of slides)
Stable Matchings: The GaleShapley Algorithm
(slides 18)

Week 10 
Mar. 9 

slides continued (up to 31)

Mar. 11 

slides continued (rest of slides)
Extremal Graph Theory
(slides 126)

Chapter 99.2 (+ Ramsey Numbers, not in the book)

Mar. 13 

Week 11 
Wed. Mar. 18 
Final exam, 36 p.m.
