Math 38. Graph Theory

The final will be a take-home exam, handed out on Friday, May 26 and due on Wednesday, May 31.

This course will cover the fundamental concepts of Graph Theory: simple graphs, digraphs, Eulerian and Hamiltonian graphs, trees, matchings, networks, paths and cycles, graph colorings, and planar graphs. Famous problems in Graph Theory include: Minimum Connector Problem (building roads at minimum cost), the Marriage Problem (matching men and women into compatible pairs), the Assignment Problem (filling n jobs in the best way), the Network Flow Problem (maximizing flow in a network), the Committee Scheduling Problem (using the fewest time slots), the Four Color Problem (coloring maps with four colors so that adjacent regions have different colors), and the Traveling Salesman Problem (visiting n cities with minimum cost).

This syllabus is subject to change, but it should 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	Counting spanning trees and the matrix tree theorem, minimal spanning trees and shortest paths
Week 5	3.1, 3.3	Matchings, Hall's theorem and coverings, maximum matchings, factors
Week 6	4.1, 4.2	Cuts and connectivity
Week 7	4.2, 4.3	Network flow problems, max-flow min-cut theorem
Week 8	5.1, 5.2	Vertex colorings, bounds on chromatic numbers and Mycielski's construction
Week 9	5.3, 6.1	Chromatic polynomials, chordal graphs, planar graphs
Week 10	6.2, 6.3	Euler's formula and Kuratowski's theorem, five and four colored theorems

The course grade will be based on the homework (20%), two midterms (25% each), a final exam (25%), and class participation (5%).

There will be homework due every week. It will consist typically of a reading assignment (of the part of the book covered in class) and some problems. Collaboration in the homework is permitted, but you are not allowed to copy someone else's work. The solutions must be written individually. You have to mention on your problem set the names of the students that you worked with.

Exams

On the midterms and the final exam you must work on the problems on your own. No collaboration permitted in the exams.

Students with disabilities: Students with learning, physical, or psychiatric disabilities enrolled in this course that may need disability-related classroom accommodations are encouraged to make an office appointment to see me before the end of the second week of the term. All discussions will remain confidential, although the Student Disability Services office may be consulted to discuss appropriate implementation of any accommodation requested.