Home
Teaching
Papers
Presentations
Software
Other

MATH 412  Graph Theory
Fall 2012
Books on reserve
Exams
The midterm exams will be on Mondays from 79 in Altgeld 145 (same as the problem sessions). On exam weeks, the problem sessions will be on Tuesdays, 57 (Altgeld 145).
 Exam 1: September 17th. Covers all of Chapter 1.
 Exam 2: October 15th. Covers Chapters 2, 3, and Section 4.1.
 Exam 3: November 12th. covers Chapters 4 and 5.
 Exam 4: (Optional) December 10th. Comprehensive.
Exam advice
Homeworks
Collaborative Study Sessions
NonExam Weeks: Monday 79pm, Altgeld 145.
Exam Weeks: Tuesday 57pm, Altgeld 145.
Advice on writing homework solutions
Topics Discussed
 08/27  1.1: What is a graph? Graphs as Models.
 08/29  1.1: Graphs as Models, Matrices and Isomorphism.
 08/31  1.1: Matrices and Isomorphism, Decomposition and Special Graphs. 1.2: Paths, Cycles, and Trails.
 09/05  1.2: Connectivity and Bipartite Graphs
 09/07  1.2: Eulerian Circuits. 1.3: Degree sum formula
 09/10  1.3: Counting and Bijctions, Extremal and Optimization problems, Mantel's Theorem.
 09/12  1.3: Graphic degree sequences, HavelHakimi Theorem. 1.4: Directed graphs.
 09/14  1.4: Directed degrees, de Bruijn Cycles, Tournaments.
 09/17  2.1: Characterization of Trees, Spanning Trees.
 09/19  2.1: Distance, diameter, radius. Paths and Stars are extremal. 2.2: Cayley's Formula.
 09/21  2.2: MatrixTree Theorem, Graceful Labelings.
 09/24  2.2: More on Graceful Labelings, 2.3: Kruskal's Algorithm.
 09/26  2.3: Dijkstra's Algorithm, BreadthFirst Search, Chinese Postman Problem.
 09/28  3.1: Hall's Theorem, KönigEgerváry Theorem, Weak and Strong Duality.
 10/01  3.1: Independence number and edge covers. 3.3: Tutte's Contition and Theorem.
 10/03  3.3: Tutte's Theorem (continued). BergeTutte Formula, Petersen's Theorem.
 10/05  3.2: Augmenting Path Algorithms, Weighted Matchings/Covers, Hungarian Algorithm.
 10/08  3.2: Correctness of Hungarian Algorithm, Stable Matchings, 3.3: Petersen's Corollary.
 10/10  3.3: 2factors in Regular graphs. 4.1: Definitions of connectivity.
 10/12  4.1: Examples of connectivity. Edgeconnectivity. Blocks.
 10/15  4.1: Properties of Blocks, 4.2: Structure of 2connected graphs.
 10/17  4.2: Structure of kconnected graphs, internallydisjoint paths, Menger's Theorem and variants.
 10/22  4.2: Proof of Menger's Theorem and Corollaries.
 10/24  4.3: Network flows, faugmenting paths, source/sink cuts.
 10/26  4.3: FordFulkerson Algorithm, MaxFlow/MinCut.
 10/29  4.3: Applications of Integral MaxFlow/MinCut. 5.1: Vertex Coloring, Lower Bounds.
 10/31  5.1: Upper bounds using greedy coloring. Interval Graphs. GallaiRoyVitaver Theorem.
 11/01  5.1: Proof of GallaiRoyVitaver, Brooks' Theorem, Mycielski's Construction.
 11/07  5.2: Properties of Mycielski's Construction, Turán's Theorem.
 11/09  5.2: Structure of kcritical graphs.
 11/13  6.1: Planar Embeddings, Dual Graphs.
 11/15  6.1: Outerplanar Graphs, Euler's Formula.
 11/17  6.2: Kuratowski's Theorem.
 11/26  6.3: The 6, 5, and 4Color Theorems, Kempe Chains.
 11/28  6.3: Thickness, Crossing Number, Guy's Theorem.
