include "../../include.php"; ?>
1. Aug 25, Wed.
course overview and logistics; Sec 1.1: definition of graph; Konigsberg bridge problem; graphs as models: acquaintance relations, job assignment, scheduling, coloring
2. Aug 27, Fri. definition of subgraphs and connected; matrix representations; isomorphism; handshaking lemma; max number of edges in a simple graph on n vertices; decomposition
3. Aug 30, Mon. Petersen graph; Sec 1.2: def of walks, trails, and paths; Lemma 5; Prop 11; cut-edges and cut-vertices; Thm 14; bipartite graphs; Lemma 15
4. Sep 1, Wed. Konig's Thm; Eulerian circuits; Lemma 25; Thm 26; proof by extremality; Lemma 31 and alternate proof of Thm 26; drawing a graph without lifting the pen
5. Sep 3, Fri. Sec 1.3: degrees, average degree; definition and properties of the hypercube; extremal problems, Prop 13, Prop 15, sharpness, optimization problems, Thm 19
Sep 6, Mon. Labor Day, no class.
6. Sep 8, Wed. Mantel's Thm; degree sequences; necessary and sufficient condition for general graphs; Havel-Hakimi Thm
7. Sep 10, Fri. Berge's Thm on 2-switches; digraphs and basic properties; Eulerian digraphs; De Bruijn cycles
8. Sep 13, Mon. tournaments; Prop 30 existence of kings; Exercise 1.3.36 on the existence of more than one king; Sec 2.1: definition of trees; Lemma 3; Thm 4; Cor 5; Prop 6
9. Sep 15, Wed. Prop 8; distance, diameter, eccentricity, radius, and center; examples; Thm 11; Thm 13 center of a tree
10. Sep 17, Fri. Sec 2.2: Cayley's Formula and Prufer codes; Cor 4; recursion formula for counting spanning trees; statement of Matrix Tree Thm
11. Sep 20, Mon. proof idea of Matrix Tree Thm; tree decompositions of K_n; graceful labelings; Sec 2.3: Kruskal's Algorithm
12. Sep 22, Wed. Prim's Algorithm; Dijkstra's Algorithm
13. Sep 24, Fri. Chinese Postman Problem; Sec 3.1: matchings; M-alternating paths and M-augmenting paths
14. Sep 27, Mon. Lemma 9; Thm 10; Hall's Thm; Cor 13; vertex covers
15. Sep 29, Wed. Konig-Egervary Thm; independent sets and edge covers; Gallai's Thm; Konig's Thm
16. Oct 1, Fri. Sec 3.2: maximum bipartite matching algorithm; stable matchings and Gale-Shapley algorithm
17. Oct 4, Mon. Sec 3.3: matchings in non-bipartite graphs; Tutte's 1-factor thm; Berge-Tutte formula
18. Oct 6, Wed. Cor 8; Thm 9; Sec 4.1: connectivity, definitions; Harary graphs and Thm 5; edge-connectivity
19. Oct 8, Fri. Thm 9 relating connectivity, edge-connectivity, and minimum degree; Thm 11 on 3-regular graphs; minimum size of a component in G-F when |F|
20. Oct 11, Mon. bonds and Prop 15; blocks and block decomposition; Prop 19; block-cutpoint graph is acyclic; Sec 4.2: 2-connected graphs; Thm 2
21. Oct 13, Wed. Thm 4 on equivalent characterizations of two-connected graphs; subdivisions; ear decomposition of two-connected graphs; ear decomposition of two-edge-connected graphs; Robbins Thm on when graphs have strong orientations
Oct 15, Fri. No lecture.
Oct 18, Mon. Class cancelled courtesy of Northwest airlines.
22. Oct 20, Wed. x,y-cuts; kappa(x,y) and lambda(x,y); Menger's Thm
23. Oct 22, Fri. Thm 21; Sec 4.3: network flows; f-augmenting paths; source-sink cuts; Cor 8 (weak duality)
24. Oct 25, Mon. Ford-Fulkerson algorithm; Max-flow Min-cut Thm; integral flows; edge Menger Thm from Max-flow Min-cut Thm
25. Oct 27, Wed. Max-flow Min-cut Thm from edge Menger Thm; application: baseball elimination; circulations
26. Oct 29, Fri. Sec 5.1: colorings; chromatic, independence, and clique numbers; coloring cartesian products; greedy algorithm; interval graphs
27. Nov 1, Mon. Mycielski construction; k-critical graphs; Szekeres-Wilf Thm; Gallai-Roy-Vitaver Thm
28. Nov 3, Wed. Brooks' Thm; Sec 5.2: properties of k-critical graphs
29. Nov 5, Fri. edge-connectivity of k-critical graphs; forced subdivisions; Hajos and Hadwiger conjectures
30. Nov 8, Mon. Turan's Thm; Sec 5.3: simplicial vertices; simplicial elimination ordering
31. Nov 10, Wed. chordal graphs and perfect graphs
32. Nov 12, Fri. Sec 6.1: planar graphs; dual graph; Prop 13; Thm 14; Thm 16; outerplanar graphs; Props 18, 19, and 20
33. Nov 15, Mon. Euler's formula; edge bound for planar graphs; 6 color thm; platonic solids
34. Nov 17, Wed. Sec 6.2: Kuratowski's Thm
Nov 19, Fri. No class.
Nov 22-26 Thanksgiving break, no class.
35. Nov 29, Mon. Sec 6.3: Five Color Thm; Four Color Thm; Sec 7.1: edge colorings; greedy bounds; line graphs; Konig's Thm on edge colorings of bipartite graphs
36. Dec 1, Wed. chromatic index of Petersen graph; Shannon's Thm; Vizing's Thm without proof Sec 7.2: Hamiltonian cycles; necessary condition
37. Dec 3, Fri. Dirac's Thm; Ore's Thm; Hamiltonian closure; Bondy-Chvatal Thm; Chvatal's Thm; sharpness
38. Dec 6, Mon. Chvatal-Erdos Thm; Sec 7.3: Tait's Thm
Dec 8, Wed. No lecture.
39. Dec 10, Fri. Grinberg's Thm; Tutte's example
|Back||This page last modified echo date("D, F j, Y \\a\\t g:ia",getlastmod()); ?>.|