#### Graph Theory Math 452 Fall 2014 Class Log

 1. Aug 25, Mon. course overview and logistics; initial student survey; Sec 1.1: basic concepts in graph theory; definitions, simple graphs, multiple edges and loops; examples: road networks, social networks, collaboration graph; cliques, independent sets, and complements; assignment problems; bipartite graphs 2. Aug 27, Wed. k-partite graphs; scheduling and coloring; isomorphism; isomorphism is an equivalence relation; subgraphs; common graph families 3. Aug 29, Fri. Petersen graph; girth; paths; connected graphs; Sec 1.2: walks, trails, paths; "has an x,y-path" is an equivalence relation; components; cut edges; characterization of cut edges Sep 1, Mon. No class. 4. Sep 3, Wed. What is a good answer?; bipartite graphs; characterization of bipartite graphs in terms of odd cycles; eulerian circuits; necessary condition for eulerian graphs 5. Sep 5, Fri. two proofs of the characterization of eulerian graphs: induction and extremality; drawing graphs with few strokes of the pen 6. Sep 8, Mon. drawing with few strokes of the pen; Sec 1.3: degree sum formula; hypercube; extremal problems; min number of edges in a connected graph; min degree enforcing connectivity; sharpness; bipartite subgraphs with many edges 7. Sep 10, Wed. induced subgraphs; Mantel theorem; incorrect proof by induction; correct proof by counting; degree sequences; even sum necessary; allowing loops and multiple edges 8. Sep 12, Fri. Havel-Hakimi thm; Berge thm on connected space of realizations; Sec 1.4: digraphs and basic definitions; strongly and weakly connected; degree sum; eulerian digraphs; characterization 9. Sep 15, Mon. DeBruijn cycles; tournaments and kings; Sec 2.1: trees; basic definitions; lemma for induction; equivalent characterizations 10. Sep 17, Wed. equivalent characterizations, continued; basic properties of trees; spanning trees; min degree cond to force a tree as a subgraph; distance, eccentricity, diameter, and radius 11. Sep 19, Fri. center of a graph; center of a tree; Sec 2.2: Cayley's formula; Prufer codes; counting the number of labeled trees with fixed degrees 12. Sep 22, Mon. recursion for number of spanning trees; Matrix Tree Thm; proof using induction; discussion of ideas underlying the theorem; graceful labelings; Graceful Tree Conjecture 13. Sep 24, Wed. decomposition of K_{2m+1} into copies of a tree with m edges; Graceful Labeling conjecture implies the decomposition conjecture; Sec 2.3: minimum weight spanning trees; Kruskal alg and proof 14. Sep 26, Fri. Dijkstra's alg; Chinese Postman Problem; Sec 3.1: matchings; alternating and augmenting paths; symmetric difference; characterization of maximum matchings via augmenting paths 15. Sep 29, Mon. Hall's condition; Hall's thm; vertex covers; inequality between min size of vertex cover and max size of a matching 16. Oct 1, Wed. Konig-Egervary thm; independent sets and edge covers; Gallai thm 17. Oct 3, Fri. Konig's other thm; Sec 3.2: maximum bipartite matching alg; proof of correctness; maximum weighted bipartite matching; dual problem: vertex cover; equality subgraph 18. Oct 6, Mon. discussion of homework; Hungarian algorithm; example Test 1 Oct 7, Tues, 2 hours in 5-9pm in 118 Altgeld 19. Oct 8, Wed. Sage example of Hungarian algorithm; proof of termination; stable matchings; Gale-Shapley algorithm 20. Oct 10, Fri. Sec 3.3: Tutte's 1-factor thm; proof 21. Oct 13, Mon. discussion of test; Berge-Tutte thm; discussion of Edmonds's Blossom algorithm and algorithm for maximum weighted matching in non-bipartite graphs 22. Oct 15, Wed. Petersen thm on cubic graphs; Petersen thm on 2-factors; Sec 4.1: definition of connectivity 23. Oct 17, Fri. Harary graphs; edge connectivity; edge cuts; kappa <= kappa'; 3-regular graphs Oct 20, Mon. Fall Break -- no class 24. Oct 22, Wed. edge cuts when kappa' is small; bonds; blocks; Sec 4.2: 2-connected graphs; internally disjoint paths 25. Oct 24, Fri. Whitney thm; expansion lemma; other characterizations of 2-connected graphs; subdivisions 26. Oct 27, Mon. expansion lemma; ear decomposition; 2-edge-connected graphs; closed ear decomposition; connectivity for digraphs 27. Oct 29, Wed. Robbins thm; Menger thm 28. Oct 31, Fri. different forms of Menger thm; global version of Menger thm; edge versions 29. Nov 3, Mon. fan lemma; Dirac thm; Sec 4.3: network flows; definitions; f-augmenting paths 30. Nov 5, Wed. edge cuts; weak duality; Ford-Fulkerson algorithm; correctness and finiteness; strong duality; decomposition of integral flows into unit flows; directed edge Menger thm from Max Flow-Min Cut thm 31. Nov 7, Fri. other versions of Menger's theorem; baseball elimination; Sec 5.1: scheduling and coloring; definition 32. Nov 10, Mon. bounds with clique number and independence number; greedy coloring; degeneracy; Szekeres-Wilf thm 33. Nov 12, Wed. Brooks's Thm; Sec 5.2: Mycielski construction 34. Nov 14, Fri. review of Mycielski construction; maximum and minimum number of edges in a k-chromatic graph on n vertices; Turan thm 35. Nov 17, Mon. k-critical graphs; properties of colorings; minimum size of cuts; edge-connectedness Test 2 Nov 18, Tuesday evening in 118 Avery 36. Nov 19, Wed. S-lobes; subdivisions; Dirac thm; Hajos conjecture; Hadwiger conjecture 37. Nov 21, Fri. Sec 7.1: edge coloring; chromatic index; bounds from the chromatic number of the line graph; Vizing thm 38. Nov 24, Mon. finished proof of Vizing thm; edge-coloring complete graphs; edge-coloring bipartite graphs; fat triangle; Shannon thm Nov 26, Wed. -- Nov 28, Fri. Thanksgiving break - no class 39. Dec 1, Mon. Sec 6.1: planar graphs and plane graphs; K3,3 is not planar; planar duals; outerplanar graphs 40. Dec 3, Wed. Euler's formula; embedding on the sphere; Platonic solids; edge bound; Sec 6.2: subdivisions; Kuratowski thm 41. Dec 5, Fri. proof of Kuratowski theorem 42. Dec 8, Mon. Sec 6.3: 6-color thm; 5-color thm; 4-color thm; embedding graphs on surfaces of higher genus; Heawood formula 43. Dec 10, Wed. Sec 7.2: Hamiltonian cycles; basic necessary conditions; Dirac thm; Ore thm 44. Dec 12, Fri. Sec 7.3: Tait's thm; Grinberg's thm; Tutte counterexample Dec 18, Thu., 10am-noon Final Exam