MATH 412, GRAPH THEORY - Spring 2005

Summary of Lectures

This page contains a summary of the lectures in this course for Spring 2005. 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/19: 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/21: Sec 1.1. Incidence and adjacency matrices, isomorphism and isomorphism classes, graph decomposition, Petersen graph (structure, girth, no spanning cycle).
Lec 3, Mon 1/24: Sec 1.2. Walks and trails, paths, connected graphs and components, characterizations of cut-edges and bipartite graphs.
Lec 4, Wed 1/26: 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/28: Sec 1.3. Degree-sum Formula and bijective arguments, extremal problems (disconnected graphs and large bipartite subgraphs).
Lec 6, Mon 1/31: Sec 1.3. Local minimum (large bipartite subgraph), Mantel's Theorem (triangle-free graphs), induction trap, degree lists for multigraphs.
Lec 7, Wed 2/2: Sec 1.3-4. Graphic lists (Havel-Hakimi Theorem), 2-switches (characterization of graphs with same degrees), terminology for digraphs (examples, paths, degrees).
Lec 8, Fri 2/4: Sec 1.4. Eulerian digraphs (Eulerian circuits, de Bruijn cycles), orientations and tournaments (kings), games and digraph kernels.

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

Lec 14, Fri 2/18: Sec 3.1. Matchings (examples, augmenting paths), Hall's Theorem, Marriage Theorem.
Lec 15, Mon 2/21: Sec 3.1. Min-max theorems, Konig-Egervary, Gallai, Konig's Other Theorem.
Lec 16, Wed 2/23: Sec 3.2. Augmenting path alg, weighted matching & Hungarian Method (example).
Lec 17, Fri 2/25: Sec 3.2. Proof of Hungarian method, stable matching and proposal algorithm.
Lec 18, Mon 2/28: Sec 3.3. Tutte 1-factor Theorem, Berge-Tutte Formula, Petersen Theorem for 3-regular graphs.

Lec 19, Wed 3/2: Sec 3.3-4.1. 2-factors in regular graphs of even degree, f-factor reduction, connectivity definitions, examples up to hypercube
Lec 20, Fri 3/4: Sec 4.1. Harary graphs, edge connectivity, edge cuts, bonds, blocks.
Lec 21, Mon 3/7: Sec 4.2. 2-connected & 2-edge-connected graphs (Whitney's Theorem, ear decomposition, subdivisions, Robbins' Theorem).
Lec 22, Wed 3/9: Sec 4.2. Menger's Theorem and variations (pairwise internally disjoint paths, line graphs, edge-disjoint, digraphs, global versions).
Lec 23, Fri 3/11: Sec 4.2. connectivity of 3-regular graphs, Fan Lemma, cycles in k-connected graphs (Dirac), network flow models (definitions, augmenting paths)
Lec 24, Mon 3/14: Sec 4.3. Network flow (cuts, duality, labeling algorithm, Max Flow = Min Cut, integrality)

Lec 25, Wed 3/16: Sec 4.3-5.1. Network flow applications (Menger's Theorem, baseball elimination); vertex coloring (definitions, examples, elementary bounds).
Lec 26, Fri 3/18: Sec 5.1. Join and cartesian product, greedy coloring algorithm, interval graphs, degeneracy, Szekeres-Wilf bound.
Lec 27, Mon 3/28: Sec 5.1. Gallai-Roy-Vitaver-Hasse Theorem (finish), Brooks' Theorem, Mycielski's Construction.
Lec 28, Wed 3/30: Sec 5.2. extremal problems for chromatic number, Turan's Theorem, application, start color-critical.
Lec 29, Fri 4/1: Sec 5.2. Color-critical graphs (elementary properties, edge-connectivity), K4-subdivisions in 4-chromatic graphs.
Lec 30, Mon 4/4: Sec 5.3. chromatic polynomial (formulas and properties, up to inclusion-exclusion).
Lec 31, Wed 4/6: Sec 5.3. Simplicial elimination orderings, chordal graphs, perfect graphs.

Lec 32, Fri 4/8: Sec 6.1. Planar graphs, K5 and K, duals of planar graphs, cycles vs. bonds, bipartite planar graphs, outerplanar graphs.
Lec 33, Mon 4/11: Sec 6.1. Euler's Formula, edge bounds, Platonic solids.
Lec 34, Wed 4/13: Sec 6.2. Kuratowski's Theorem.
Lec 35, Fri 4/15: Sec 6.2-3. Planarity algorithm, 5-Color Theorem, Kempe's proof.
Lec 36, Mon 4/18: Sec 6.3. Ideas of 4-Color Theorem, crossing number, surfaces of higher genus, Heawood Formula.

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