Math 38: Graph Theory

The final exam for Math 38 will be in our regular classroom, Haldeman 028. It's at 3pm Sunday June 1; you'll have 3 hours to complete the exam, but it's actually designed to take only two.

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

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

	Chapters	Brief Description
Week 1	1.1	Definitions; bipartite graphs; chromatic number; adjacency matrix; isomorphism; decomposition; connectedness; subgraphs and induced subgraphs
Week 2	1.2, 1.3	Path versus walk; cycles; cut-edge and cut-vertex; TONCAS for Eulerian property; sum of degrees; extremality; induction
Week 3	1.4	Paths; cycles; strong digraphs; Eulerian digraphs
Week 4	2.1, 2.2	Equivalent definitions of tree; distance and diameter; Cayley's Theorem and Pruefer code; recurrence for counting spanning trees; matrix-tree theorem (not proof); BEST Theorem and proof; graceful tree conjecture
Week 5	2.3	Kruskall's algorithm and reverse version; Dijkstra's algorithm
Week 6	3.1	Maximal, maximum and perfect matchings; augmenting paths; Hall's marriage theorem; min-max theorems: vertex cover versus matchings; Koenig's Theorem on edge-coloring a bipartite multigraph [not in text]
Week 7	4.1, 4.2, 4.3	Edge-connectivity; blocks; k-connectedness; 2-connected graphs; connectivity in digraphs; Menger's Theorem (not proof); line graphs; feasible and maximal flows; min flow/max cut theorem (not proof)
Week 8	5.1, 5.2	Cartesian product; interval graphs; Brooks' Theorem; Mycielski's construction; color-criticality; Turan's Theorem and proof
Week 9	6.1, 6.2	Planar graphs versus plane graphs; non-planarity of K5 and K3,3; faces and the dual graph; Euler's formula; bound on number of edges; maximal planar graphs; Kuratowski's TONCAS (not proof); list coloring and Thomassen's Theorem [not in text]
Week 10	7.2	Necessary and sufficient conditions for Hamiltonicity; Dirac's Theorem; Gray code [not in text]; mid-levels problem[not in text]

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

Midterms will be in class on Monday, April 14 and Friday, May 2: make sure you don't miss those! The final will be at the scheduled 3-hour period for period 12 (MWF 12:30-1:35) classes, namely at 3:00 pm on Sunday June 1, and will be comprehensive.

There will be homework due most class meetings. It will consist typically of a reading assignment (of the part of the book covered in class) and one or two problems. Collaboration on the homework is permitted, provided the assignments are written up separately and independently. Names of those persons with whom you collaborated must be written on the assignment.

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.

Math 38. Graph Theory