Math 38. Graph Theory

Spring 2010

·        Instructor:         Sergi Elizalde

·        Lectures:           MWF 12:30-1:35 in Kemeny 108

·        X-period:           Tu 1:00-1:50

·        Office Hours:    M 11-12:30, Th 2:30-3:30.

·        Office:               Kemeny 332

·        Email:               

·        Phone:               646-8191

Announcements

Here is this week's homework assignment.

The class on Friday, May 28 will be moved to the X-hour on Tuesday, May 25.

The take-home final exam will be handed out on Wednesday, May 26, and due on June 2, the last day of class. It will cover everything we have done up to Chapter 5 (included).

The grader for the course is Will Chen.

Course description

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: the 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).

Textbook

Introduction to Graph Theory by Douglas B. West, Second edition (available at Wheelock Books).

Tentative syllabus

This syllabus is subject to change, but it should give you an idea of the topics I am planning to cover.


 

Chapters

Brief Description

Week 1

1.1, 1.2

Definitions, examples of problems in graph theory, isomorphisms. Paths, walks, cycles, components, bipartite graphs, Eulerian graphs.

 

Week 2

1.3, 1.4

Vertex degrees, extremal problems, degree sequences. Directed graphs, de Bruijn cycles, orientations.

 

Week 3

2.1

Trees and distance, spanning trees, radius and diameter.

 

Week 4

2.2

Enumeration of trees, Cayley’s formula, Prüfer code. Counting spanning trees, deletion-contraction, the matrix tree theorem, graceful labelings.

 

Week 5

2.3

Minimum spanning trees (Kruskal’s algorithm), shortest paths (Dijkstra’s algorithm).

Week 6

3.1

Matchings, Hall's theorem, min-max theorems, maximum matchings, independent sets,  vertex and edge coverings.

 

Week 7

4.1, 4.2
 

Cuts, connectivity, edge-connectivity, blocks, k-connected graphs, Menger’s theorem, line graphs .

Week 8

4.3

Network flow problems, max-flow min-cut theorem, Ford-Fulkerson algorithm.
 

Week 9

5.1, 5.3

Vertex colorings, bounds on chromatic numbers. Chromatic polynomials.
 

Week 10

6

Planar graphs, Euler's formula, Kuratowski's theorem, five and four color theorems.
 

 

Grading

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

Homework

There will be homework due roughly every week. It will consist typically of a reading assignment (of the part of the book covered in class) and some problems. All the homework assignments are posted here. You are encouraged to collaborate on the homework, but what you write has to be your own understanding of how to do the problem. You must state what sources you have consulted, with whom you have collaborated, and from whom you have received help. No late homework will be accepted.

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.