Math 454
Graph Theory and Applications
Spring 2018
Meetings: TR 1:50-3:05Classroom: 239 Stuart Building
Syllabus: syllabus, hw suggestions
E-mail: breiniger (at) iit (dot) edu
My office: 110 Rettaliata Engineering Building
Office hours: TBD, and by appointment
Homework, Exams
(Homework solutions were posted to Blackboard, but not made available here since a large portion of it came directly from the text.)
Schedule
| Date | Topics |
| 4/30 or 5/3 | Final Exam - Choose either Monday 4/30 or Thursday 5/3. 2-4pm in RE121 on either date. |
| 4/26 | Bonus topics: Random graphs (Erdős-Rényi, preferential attachment, geometric), Earth-Moon problem, toroidal graphs, Hadwiger-Nelson problem (recent progress) Review (notation, Ford-Fulkerson) 7.2: Chvátal-Erdős condition |
| 4/24 | 7.3: Tait's Theorem 7.2: Petersen is not Hamiltonian; sufficient conditions (Dirac, Ore) |
| 4/19 | 7.2: Hamiltonian cycles, necessary condition 7.1: edge colorings, line graphs, Vizing's Theorem (only first part of proof), class 1/class 2 graphs |
| 4/17 | 6.3: chromatic number of planar graphs: easy proof that 6 colors suffice, Kempe chain proof that 5 colors suffice, statement that 4 colors suffice; nothing else from this section 6.2: subdivisions, Kuratowski's Theorem (w/o proof) 6.1: equivalence for plane graphs of bipartite, even faces, Eulerian dual |
| 4/12 | Exam 2 - Chapters 5 (+list coloring), 3 |
| 4/10 | 6.1: planar graphs, plane graphs, faces, dual graph; Euler's formula and edge-bound for simple (triangle-free) planar graphs |
| 4/5 | 4.3: network flows, duality with source-sink cuts, Fork-Fulkerson Algorithm, Max-flow=Min-cut (proof idea), Integrality (w/o proof) 4.2: versions of Menger's Theorem for edge-connectivity, digraphs, and global versions (w/o proofs) |
| 4/3 | 4.2: equivalent characterizations of 2-connected graphs (NOT ear decompositions); statement of Menger's Theorem (local version) 4.1: bonds, blocks, block-cutpoint tree |
| 3/29 | 4.1: definitions, connectivity of hypercubes; relationship between connectivity, edge-connectivity, and minimum degree; 3-regular graphs have connectivity=edge-connectivity |
| 3/27 | 3.3: Tutte's 1-Factor Theorem (w/o proof), maximum matching size in terms of "deficiency" (w/o proof), Petersen's 3-regular cut-edge-free sufficient condition, and Petersen's 2-factor theorem (NOT section 3.2) 3.1: vertex covers and the Min-max relation to matchings; König-Egerváry theorem (NOT subsection on independence-edge cover min-max relation) |
| 3/22 | 3.1: augmenting paths, Hall's Matching Theorem |
| 3/20 | 3.1: definitions, examples 5.2: finished proof of Mycielski properties; Turán's Theorem (NOT subsections on color-critical properties or forced subdivisions) reviewed exam |
| 3/8 | Exam 1 - Chapters 1, 2 |
| 3/6 | Review? 5.2: Mycielski's construction 5.1: critical graphs, a coloring bound using orientations |
| 3/1 | 8.4: introduction to list coloring (p.408) 5.1: upper bounds on chromatic number, using the greedy algorithm, including Brooks' Theorem and the chromatic number of interval graphs |
| 2/27 | 5.1: (proper) colorings, chromatic number, color-critical graphs; examples and lower bounds; Cartesian product of graphs |
| 2/22 | 2.3: proof of correctness for Kruskal; Dijkstra's algorithm for Shortest Paths, breadth-first-search, Chinese Postman Problem |
| 2/20 | 2.3: weighted graphs, Kruskal's algorithm for Minimum Spanning Tree 2.2: enumerating spanning trees, edge contraction, Matrix Tree theorem (no proof) comments on HW4#2 |
| 2/15 | (Pelsmajer) 2.2: Cayley's formula, Prüfer codes 2.1: Wiener index and its max/min values for trees and for all graphs |
| 2/13 | 2.1: another edge exchange for spanning trees, a condition for finding a fixed tree as a subtree; distance, eccentricity, diameter, radius, center |
| 2/8 | 2.1: introduction to trees, equivalent conditions, edge exchange for spanning trees 1.4: orientations, tournaments and kings |
| 2/6 | 1.4: directed graph definitions, Eulerian digraphs, de Bruijn cycles |
| 2/1 | 1.3: degree sequences of (loopless/simple) graphs, Havel-Hakimi Exercises 1.3.16 and 1.3.19 (interesting constructions) |
| 1/30 | 1.3: large bipartite subgraphs, algorithmic proofs, Mantel's Theorem, induction for graphs, the induction trap, intro to degree sequences |
| 1/25 | (Pelsmajer) 1.3: Degree-sum Formula, counting, hypercubes, introduction to extremal problems |
| 1/23 | 1.2: Eulerian circuits, maximal paths, decomposition into cycles/trails |
| 1/18 | 1.2: components, cut vertices/edges, induced subgraphs, bipartite graphs |
| 1/16 | 1.2: walks contain paths 1.1: Petersen graph, some properties thereof Intro, syllabus |
| 1/9,11 |
(Kaul) |
Content migrated from Blackboard January 30, 2019