MATH 312, GRAPH THEORY - Spring 2004

Summary of Lectures

This page contains a summary of the lectures in this course for Fall 2004. It lists only the topics discussed in each lecture. The text provides extensive discussion and additional material, so no additional notes are provided here.

An indication of what material will be covered in the remainder of the course can be obtained from the Lecture Summary for Spring 2002. The schedule will be quite similar.

Lec 1, Wed 1/21: Sec 1.1. Course requirements, graph definitions and models (acquaintance relation, job assignments and bipartite graphs, scheduling and graph coloring, road networks and paths).
Lec 2, Fri 1/23: Sec 1.1. Incidence and adjacency matrices, isomorphism and isomorphism classes, graph decomposition, Petersen graph (structure, girth, no spanning cycle).
Lec 3, Mon 1/26: Sec 1.2. Walks and trails, paths, connected graphs and components, characterizations of cut-edges and bipartite graphs.
Lec 4, Wed 1/28: Sec 1.2. Covering complete graphs by bipartite graphs, extremality and maximal paths, Eulerian circuits and even graphs, decompositions into cycles and into trails.
Lec 5, Fri 1/30: Sec 1.3. Degree-sum Formula and bijective arguments, extremal problems (connected graphs and large bipartite subgraphs).
Lec 6, Mon 2/2: Sec 1.3. Local minimum (large bipartite subgraph), Mantel's Theorem (triangle-free graphs), induction trap, degree sequences for multigraphs.
Lec 7, Wed 2/4: Sec 1.3-4. Graphic sequences (Havel-Hakimi Theorem), 2-switches (characterization of graphs with same degrees), terminology for digraphs (examples, paths, degrees).
Lec 8, Fri 2/6: Sec 1.4. Eulerian digraphs (Eulerian circuits, de Bruijn cycles), orientations and tournaments (kings).

Lec 9, Mon 2/9: Sec 2.1. Trees (characterizations and additional properties).
Lec 10, Wed 2/11: Sec 2.1. Distance and diameter (definitions and examples, center of trees), distance sum (Wiener index in trees).
Lec 11, Fri 2/13: Sec 2.1-2. Bridg-it, Cayley's Formula, trees with given degrees.
Lec 12, Mon 2/16: Sec 2.2. Counting spanning trees (recurrence, Matrix Tree Theorem), graceful labelings.
Lec 13, Wed 2/18: Sec 2.3. Minimum spanning trees (Kruskal's Algorithm), shortest paths (Dijkstra's Algorithm, Chinese Postman Problem).

Lec 14, Fri 2/20: Sec 3.1. Matchings (examples, augmenting paths), Hall's Theorem, Marriage Theorem.
Lec 15, Mon 2/23: Sec 3.1. Min-max theorems, Konig-Egervary, Gallai, Konig's Other Theorem.
Lec 16, Wed 2/25: Sec 3.2. Augmenting path alg, weighted matching & Hungarian Method.
Lec 17, Fri 2/27: Sec 3.2. Proof of Hungarian method, stable matching and proposal algorithm.
Lec 18, Mon 3/1: Sec 3.3. Tutte 1-factor Theorem and applications.
Lec 19, Wed 3/3: Sec 3.3-4.1. f-factor reduction, connectivity definitions, hypercube, Harary graphs.

Lec 20, Fri 3/5: Sec 4.1. Edge connectivity, edge cuts, bonds, blocks.
Lec 21, Mon 3/8: Sec 4.2. 2-connected & 2-edge-connected graphs (Whitney's Theorem, ear decomposition, subdivisions, Robbins' Theorem).
Lec 22, Wed 3/10: Sec 4.2. Menger's Theorem (pairwise internally disjoint paths).
Lec 23, Fri 3/12: Sec 4.2. Digraph connectivity, Menger variations, Fan Lemma, cycles in k-connected graphs.
Lec 24, Mon 3/15: Sec 4.3. Network flow (definitions, cuts, duality, labeling algorithm, Max Flow = Min Cut)
Lec 25, Wed 3/17: Sec 4.3-5.1. Network flow applications (integrality, Menger's Theorem, baseball elimination); vertex coloring (definitions, examples).

Lec 26, Fri 3/19: Sec 5.1. Bounds on chromatic number, greedy coloring algorithm, color critical graphs, Szekeres-Wilf bound.
Lec 27, Mon 3/29: Sec 5.1. Gallai-Roy-Vitaver Theorem, Brooks' Theorem.
Lec 28, Wed 3/31: Sec 5.2. Mycielski's Construction, Turan's Theorem, application.
Lec 29, Fri 4/2: Sec 5.2. Color-critical graphs (elementary properties, edge-connectivity), K4-subdivisions in 4-chromatic graphs.
Lec 30, Mon 4/5: Sec 5.3. chromatic polynomial (formulas and properties).
Lec 31, Wed 4/7: Sec 5.3. Simplicial elimination orderings, chordal graphs, perfect graphs.

Lec 32, Fri 4/9: Sec 6.1. Planar graphs, K5 and K3,3, duals of planar graphs, cycles vs. bonds, bipartite planar graphs.
Lec 33, Mon 4/12: Sec 6.1. Outerplanar graphs, Euler's Formula, edge bounds, Platonic solids.
Lec 34, Wed 4/14: Sec 6.2. Kuratowski's Theorem.
Lec 35, Fri 4/16: Sec 6.2-3. Planarity algorithm, 5-Color Theorem, Kempe's proof.
Lec 36, Mon 4/19: Sec 6.3. Ideas of 4-Color Theorem, embeddings on surfaces of higher genus.

Lec 37, Wed 4/21: Sec 7.1. Edge-coloring (examples, bipartite graphs).
Lec 38, Fri 4/23: Sec 7.1. Vizing's Theorem for simple graphs.
Lec 39, Mon 4/30: Sec 7.2. Hamiltonian cycles (necessary condition, Dirac's Theorem, closure).
Lec 40, Wed 5/2: Sec 7.2. Chvatal's Condition, Chvatal-Erdos Theorem.
Lec 41, Fri 5/4: Sec 7.3. Tait's Theorem, Grinberg's Theorem.