Math 38 Homepage

Due Date	Date Assigned	Topics Covered	Homework*
-/-	03/29	Introduction: Examples and Applications of Graph Theory	Read Chapter 1.1
04/09	03/31	Basic Definitions and Graph Isomorphisms	Read Chapter 1.2 Problems Chapter 1.1 #10,13,16,21,29,30
	04/02	Walks, Cycles and Bipartite Graphs	Read Chapter 1.3 Problems Chapter 1.2 #2,8,10,17,20,38
	04/05	Components, Cut-edges, Eulerian Graphs	Problems Chapter 1.2 #11,27,30
04/16	04/07	Vertex Degrees and Degree Sequences	Read Chapter 1.4 Problems Chapter 1.3 #1,8,12,14,18,31
	04/09	Directed Graphs	Read Chapter 2.1 Problems Chapter 1.4 #9,15,19
	04/12	Eulerian Digraphs and Trees	Read Chapter 2.2 Problems Chapter 1.4 #26,27 Problems Chapter 2.1 #2,6,19
04/23	04/13	Trees and Distance	Problems Chapter 2.1 #11,23,27,32
	04/14	Counting Trees and Prüfer Codes	Read Chapter 2.3 Problems Chapter 2.2 #1,7,8
	04/16	Counting Spanning Trees and the Matrix Tree Theorem	Problems Chapter 2.2 #12,15
04/30	04/19	Minimal Spanning Trees and Shortest Paths	Read Chapter 3.1 Problems Chapter 2.3 #2,3,16
	04/21	Matchings	Read Chapter 3.2 Problems Chapter 3.1 #8,10,18,28
	04/23	Hall's Theorem and Coverings	Problems Chapter 3.1 #1,5,24 (See Example 3.1.2),26,29
05/07	04/26	Maximum Matchings	Read Chapter 4.3 Problems Chapter 3.2 #1,5,6
	04/28	Maximum Weighted Matchings
	04/30	Hungarian Algorithm	Read Chapter 5.1 Problems Chapter 4.3 #1,2,3
05/14	05/03	Network Flow Problems
	05/05	Max-flow Min-cut Theorem	Problems Chapter 4.3 #11,13,14
	05/07	Vertex Colorings	Read Chapter 5.2 Problems Chapter 5.1 #1,12,14
05/21	05/10	Bounds on Chromatic Numbers and Mycielski's Construction	Read Chapter 5.3 Problems Chapter 5.1 #20,31,33 Problems Chapter 5.2 #1,9
05/21	05/12	Chromatic Polynomials	Read Chapter 6.1 Problems Chapter 5.3 #1,3,5,7,10,11
05/28	05/17	Chordal Graphs	Read Chapter 6.2 Problems Chapter 5.3 #9,18,19,24 Problems Chapter 6.1 #2,3
	05/19	Planar Graphs	Problems Chapter 6.1 #12,13,21,25
	05/21	Euler's Formula and Kuratowski's Theorem	Problems Chapter 6.1 #8,9,33
-/-	05/24	Five and Four Color Theorems	Read Chapter 7.1 Suggested Problems Chapter 6.2 #1,4,6,12
	05/26	Line Graphs and Chromatic Index	Read Chapter 7.2 Suggested Problems Chapter 7.1 #1,3,5,8,11,12,18,24,26
	05/28	Hamiltonian Cycles	Suggested Problems Chapter 7.2 #1,2,3,7,8,10,12,17
	06/02	Unsolved Problems in Graph Theory