Date 
Lecture 
Notes 
Assigned Reading 
Week 1 
1/30 
Introduction and Basic Definitions 
Notes 
Sections 1.1, 1.2 
2/1 
Common Classes of Graphs 
Notes 
Sections 1.3, 1.4 
Week 2 
2/6 
Connectivity, Bipartite Graphs 
Notes 
Sections 2.1, 2.2 
2/8 
Degrees, Regular Graphs 
Notes 
Sections 2.3, 2.4 
Week 3 
2/13 
Degree Sequences and Matrices 
Notes 
Sections 3.1, 3.2 
2/15 
Graph Isomorphism 
Notes 
Section 3.4 
Week 4 
2/20 
Trees 
Notes 
Sections 4.1, 4.2 
2/22 
Minimum Spanning Trees 
Notes 
Section 4.3 
Week 5 
2/27 
Counting Spanning Trees 
Notes 
Section 4.4 
3/1 
Connectivity 
Notes 
Sections 5.1, 5.2 
Week 6 
3/6 
Connectivity 
Notes 
Section 5.3 
3/8 
Midterm 1 (Chapters 14) 
Week 7 
3/13 
Connectivity 
Notes 
Sections 5.4 
3/15 
Connectivity 
Notes 
Sections 5.5 
Spring Break 
3/20  
3/22  
Week 8 
3/27 
Eulerian Graphs 
Notes 
Section 6.1 
3/29 
Hamiltonian Graphs 
Notes 
Section 6.2 
Week 9 
4/3 
Hamiltonian Walks 
Notes 
Sections 6.4 and 6.5 
4/5 
Digraphs 
Notes 
Section 7.1 
Week 10 
4/10 
Tournaments 

Section 7.2 
4/12 
Tournaments 
Notes 
Section 8.1 
Week 11 
4/17 
Random Walks 

Section 8.2 
4/19 
Decomposition and the Peterson Graph 
Notes 
Sections 8.3, 8.5 
Week 12 
4/24 
Planarity 
Notes 
Section 9.1 
4/26 
Midterm 2 (Chapters 58) 
Week 13 
5/1 
Planarity 

Section 9.2 
5/3 
Planarity 
Notes 
Section 9.3 
Week 14 
5/8 
The four (five) color theorem 
Notes 
Section 10.1 
5/10 
Vertex Coloring 
Notes 
Section 10.2 
Week 15 
5/15 
Edge Coloring 

Section 10.3 
5/17 
Final Exam (10:15 AM) 