Class: MW 3:004:15, MB 139
Instructor: Dr. Zach Teitler
Office: MG 233A
Phone: 2084261086
Email: zteitler@boisestate.edu
Office hours: TBA and by appointment
View course advertisement: pdf, html
Important dates:
Textbook:
Graph Theory, by Bondy and Murty, Springer, 2008.
See the blog of the book
for errata and hints to selected exercises.
Weekly schedule:
Dates  Topics (planned)  What we actually did 

Week 1  
Jan 22  Introduction  Introduction 
Week 2  
Jan 27  
Jan 29  
Week 3  
Feb 3  
Feb 5  
Week 4  
Feb 10  
Feb 12  Friendship Theorem  
Week 5  
Feb 17  President's Day  
Feb 19  Trees  
Week 6  
Feb 24  Trees, Cayley's formula  Trees and forests 
Feb 26  More proofs of Cayley's formula  Cayley's formula 
Week 7  
Mar 3  Maxflow mincut  More proofs of Cayley's formula 
Mar 5  Matchings: Berge's theorem, Hall's marriage theorem  Flows and cuts 
Week 8  
Mar 10  Maxflow mincut  
Mar 12  Corollaries of maxflow mincut  
Week 9  
Mar 17  Circulations, vector spaces associated to graphs  
Mar 19  Menger's theorem  
Week 10  
Mar 31  Matchings, Hall's marriage theorem  
Apr 2 
Written Homework:
Homeworks 15 (show/hide)
Assigned date  Assignment  Suggested problems  Due date 

Wed, 1/22/14  1 
§ 1.1 #6, 11, 12, 14, 16, 17, 18, 20, 24 
Wed, 1/29/14 
Wed, 1/29/14  2 
§ 1.2 #8, 16, (20?); § 1.3 # 1, 2, 3 § 2.1 #2, 7, 8, 13, 1617, 20 § 2.2 #3, 5, 6, 7, 11, 19, 21, 25 
Wed, 2/5/14 
Wed, 2/5/14  3 
§ 2.4 #3, 5, 7 § 3.1 #5, 7, (11) § 3.2 #3, 4 § 3.3 #1 
Wed, 2/12/14 
Short paper on open problem.  Wed, 2/19/14  
Wed, 2/19/14  4 
§ 3.3 #2, 8 § 3.4 #9 § 4.1 #7, 8, 9, 11, 12, 19 § 4.2 #10, 14 By Exercise 1.1.6(a), every finite simple graph has at least one pair of vertices with the same degree. Characterize all finite simple graphs with exactly one such pair. 
Wed, 2/26/14 
Wed, 2/26/14  5  No suggested problems (sorry).  Wed, 3/5/14 
Wed, 3/5/14  6  No suggested problems (sorry).  Wed, 3/12/14 
Wed, 3/12/14  7 
§ 7.1 #3 § 7.2 #4, 5, 6 § 7.3 #3

Wed, 3/19/14 

Wed, 4/7/14 
You may use this homework template (383 KB) if you wish. It is completely optional.