| 1 |
Aug 22 |
Introduction; Definitions and basic concepts |
1.1 |
- |
| 2 |
Aug 27 |
Cliques and Independent sets; important graphs; isomorphism |
1.1 |
HW1 assigned. |
| 3 |
Aug 29 |
Decompositions; Petersen graph |
1.1 |
- |
| 4 |
Sep 3 |
Walks, trails, paths; components; cut-vertices and cut-edges |
1.2 |
- |
| 5 |
Sep 5 |
Cut-edge characterization; lemmas on walks |
1.2 |
- |
| 6 |
Sep 10 |
Bipartite graph characterization; Eulerian circuits |
1.2 |
- |
| 7 |
Sep 12 |
Eulerian Circuits; Eulerian graph characterization |
1.2 |
HW1 due. HW2 assigned. |
| 8 |
Sep 17 |
Decomposing G into trails; degree-sum formula; hypercubes |
1.2,1.3 |
- |
| 9 |
Sep 19 |
Extremal problems; Algorithmic proofs |
1.3 |
- |
| 10 |
Sep 24 |
Mantel's Theorem; The Induction Trap |
1.3 |
- |
| 11 |
Sep 26 |
Havel--Hakimi; connectedness of 2-switch graph |
1.3 |
HW2 due; HW3 assigned. |
| 12 |
Oct 1 |
Directed graphs; deBruijn cycles |
1.4 |
- |
| 13 |
Oct 3 |
Trees; spanning trees; Bridg-it game |
2.1 |
- |
| 14 |
Oct 8 |
Cayley's Formula and Prufer codes; deletion-contraction formulas |
2.1 |
- |
| 15 |
Oct 10 |
Midterm Exam: 1.1-1.4, 2.1; Lects 1--13 |
- |
HW4 assigned. |
| 16 |
Oct 15 |
Matchings; Maximum vs. Maximal; Alternating paths |
3.1 |
HW3 due. |
| 17 |
Oct 17 |
Hall's Theorem |
3.1 |
- |
| 18 |
Oct 22 |
Vertex covers; Konig--Egervary Thm |
- |
- |
| 19 |
Oct 24 |
Tutte's Theorem |
3.3 |
- |
| 20 |
Oct 29 |
Petersen's Theorem; Vertex Cuts and Connectivity |
3.3, 4.1 |
|
| 21 |
Oct 31 |
Vertex and Edge connectivity |
4.1 |
HW4 due; HW5 assigned. |
| - |
Nov 5 |
University closed (election)-- no class. Workshop on Wednesday as usual |
- |
- |
| 22 |
Nov 7 |
Subdivisions and 2-connected graphs |
4.2 |
- |
| 23 |
Nov 12 |
Ear decompositions |
4.2 |
- |
| 24 |
Nov 14 |
Menger's Theorem |
4.2 |
HW5 due. HW6 assigned. |
| 25 |
Nov 19 |
Network Flows and Cuts; Ford--Fulkerson Algorithm |
4.3 |
- |
| 26 |
Nov 21 |
Networks Flows: undirected graphs, vertex connectivity; Vertex Coloring |
4.3,5.1 |
- |
| 27 |
Dec 3 |
Cartesian Product; Greedy Coloring Algorithm; Interval Graphs; Degeneracy
| 5.1 |
- |
| 28 |
Dec 5 |
Brooks's Theorem |
5.1 |
- |
| 29 |
Dec 10 |
Mycielski's Construction; Large girth and large chromatic number; Hajos and Hadwiger conjectures |
5.2 |
- |
| 30 |
Dec 12 |
Turan's Theorem; Erdos--Stone Theorem; ex(n, C4) upper bound |
5.2 |
HW6 due. |
| - |
Dec 20 |
Final Exam: Fri Dec 20, 11am to 1pm |
- |
- |