Math 38 - Spring 2005

Math 38 - Spring 2005

Dartmouth College

home general information syllabus homework office hours professor

This is a tentative syllabus subject to change at my discretion without prior notification. This is to give you an idea of the topics I want you to learn.

Chapters

Brief Description

Week 1

1.1-1.2

Basic definitions, isomorphisms, walks, cycles and bipartite graphs

Week 2
1.3, 1.4

Components, cut-edges, Eulerian graphs, vertex degrees and degree sequences, directed graphs

Week 3

2.1, 2.2,

Eulerian digraphs, trees and distance

Week 4

2.2, 2.3, 3.1

Counting spanning trees and the matrix tree theorem, minimal spanning trees and shortest paths,and matchings

Week 5

3.1,3.2

Hall's theorem and coverings, maximum matchings, maximum weighted matchings

Week 6

4.1, 4.2, 4.3

Hungarian algorithm, network flow problems, max-flow min-cut theorem

Week 7

5.1, 5.2

Vertex colorings, bounds on chromatic numbers and Mycielski's construction

Week 8

5.3, 6.1

Chromatic polynomials, chordal graphs, planar graphs

Week 9

6.2, 6.3

Euler's formula and Kuratowski's theorem, five and four colored theorems

Week 10

7.1 and 7.2

line graphs and chromatic index, Hamiltonian cycles

	Chapters	Brief Description
Week 1	1.1-1.2	Basic definitions, isomorphisms, walks, cycles and bipartite graphs
Week 2	1.3, 1.4	Components, cut-edges, Eulerian graphs, vertex degrees and degree sequences, directed graphs
Week 3	2.1, 2.2,	Eulerian digraphs, trees and distance
Week 4	2.2, 2.3, 3.1	Counting spanning trees and the matrix tree theorem, minimal spanning trees and shortest paths,and matchings
Week 5	3.1,3.2	Hall's theorem and coverings, maximum matchings, maximum weighted matchings
Week 6	4.1, 4.2, 4.3	Hungarian algorithm, network flow problems, max-flow min-cut theorem
Week 7	5.1, 5.2	Vertex colorings, bounds on chromatic numbers and Mycielski's construction
Week 8	5.3, 6.1	Chromatic polynomials, chordal graphs, planar graphs
Week 9	6.2, 6.3	Euler's formula and Kuratowski's theorem, five and four colored theorems
Week 10	7.1 and 7.2	line graphs and chromatic index, Hamiltonian cycles