1 |
Aug 18 |
Introduction; Definitions |
1.1 |
HW1 assigned. |
2 |
Aug 20 |
Graph isomorphisms; more definitions |
1.1 |
- |
3 |
Aug 22 |
Petersen Graph; Walks, Trails, and Paths |
1.1, 1.2 |
- |
4 |
Aug 25 |
Walks, Cut-edges, Cut-vertices |
1.2 |
- |
5 |
Aug 27 |
Induced subgraphs; Cut-edges and cycles |
1.2 |
- |
6 |
Aug 29 |
Bipartite graph characterization |
1.2 |
HW1 due; HW2 assigned. |
7 |
Sep 3 |
Maximal vs. Maximum; Eulerian graphs |
1.2 |
- |
8 |
Sep 5 |
Eulerian graphs: sufficiency; Even graphs and cycle decompositions |
1.2 |
- |
9 |
Sep 8 |
Decomposition into trails; degree sum formula; hypercubes |
1.2, 1.3 |
- |
10 |
Sep 10 |
Extremal arguments and algorithmic proofs |
1.3 |
- |
11 |
Sep 12 |
Mantel's Theorem; Inductive trap |
1.3 |
HW2 due; HW3 assigned. |
12 |
Sep 15 |
Degree sequences; Havel-Hakimi Theorem |
1.3 |
- |
13 |
Sep 17 |
Directed graphs intro; De Bruijn cycles |
1.4 |
- |
14 |
Sep 19 |
Trees |
2.1 |
- |
15 |
Sep 22 |
Prufer Codes |
2.2 |
- |
16 |
Sep 24 |
Enumerating spanning trees; Deletion-contraction; Matrix Tree Thm |
2.2 |
- |
17 |
Sep 26 |
Matchings Intro |
3.1 |
HW3 due; HW4 assigned. |
18 |
Sep 29 |
Augmenting paths |
3.1 |
- |
19 |
Oct 1 |
Hall's Theorem |
3.1 |
- |
20 |
Oct 3 |
Midterm Exam |
- |
- |
21 |
Oct 6 |
Konig--Egervary Theorem |
3.1 |
- |
22 |
Oct 8 |
Independent Sets and Covers |
3.1 |
- |
23 |
Oct 10 |
Ore's Theorem |
3.3 |
HW4 due. |
24 |
Oct 15 |
Vertex Connectivity |
4.1 |
HW5 assigned. |
25 |
Oct 17 |
Edge Connectivity |
4.1 |
- |
26 |
Oct 20 |
Vertex and Edge Connectivity; Blocks |
4.1 |
- |
27 |
Oct 22 |
Internally disjoint paths; Expansion Lemma |
4.2 |
- |
28 |
Oct 24 |
Subdivisions; Ear Decompositions |
4.2 |
- |
29 |
Oct 27 |
Closed Ear Decompositions; Local connectivity |
4.2 |
- |
30 |
Oct 29 |
Menger's Theorem |
4.2 |
- |
31 |
Oct 31 |
Flows I: Definitions, Augmenting paths |
4.3 |
HW5 due; HW6 assigned. |
32 |
Nov 3 |
Flows II: Cuts, Ford--Fulkerson |
4.3 |
- |
33 |
Nov 5 |
Flows III: Integrality, Applications |
4.3 |
- |
34 |
Nov 7 |
Graph coloring introduction |
5.1 |
- |
35 |
Nov 10 |
Cartesian product of graphs, greedy coloring |
5.1 |
- |
36 |
Nov 12 |
Class canceled |
- |
HW6 extended. |
37 |
Nov 14 |
Interval graphs, orientations and chromatic number |
5.1 |
- |
38 |
Nov 17 |
Brooks's Theorem |
5.1 |
- |
39 |
Nov 19 |
Mycielski's construction |
5.2 |
- |
40 |
Nov 21 |
Turan's Theorem |
5.2 |
HW6 due; HW7 assigned. |
41 |
Dec 1 |
Hajos and Hadwiger conjectures; planar graphs intro |
5.2, 6.1 |
- |
42 |
Dec 3 |
Duals; outerplanar graphs |
6.1 |
- |
43 |
Dec 5 |
Euler's formula; regular polyhedra; Kuratowski's theorem |
6.2 |
- |
44 |
Dec 8 |
Chromatic number of planar graphs |
6.3 |
HW7 due. |
- |
Dec 12 |
Final Exam: 8am-10am |
- |
- |