#### Class Log

 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