#### Math 412 Graph Theory Fall 2006 Class Log

 1. Aug 23, Wed. course overview and logistics; Sec 1.1: definition of graphs, examples, Konigsberg bridge problem, Ramsey problem 2. Aug 25, Fri. subgraphs and induced subgraphs, isomorphism, adjacency and incidence matrices, some common graph classes, degree sum formula 3. Aug 28, Mon. decomposition; Petersen graph; Sec 1.2: walks, trails, and paths; being connected by a path; components; maximal vs maximum 4. Aug 30, Wed. more about connected components; walks and cycles; characterization of bipartite graphs; representing a graph as a union of bipartite graphs 5. Sep 1, Fri. Eulerian circuits; characterization; proofs by extremality; drawing without lifting pencil; def of hypercube Sep 4, Mon. Labor Day - no class 6. Sep 6, Wed. Sec 1.3: more about hypercubes; extremal problems; min num edges in a connected graph; min degree to guarantee connected; sharpness of results 7. Sep 8, Fri. Mantel thm; induction; degree sequences; non-simple graphs; Havel-Hakimi condition and example 8. Sep 11, Mon. proof of Havel-Hakimi thm; Berge thm on 2-switches; Sec 1.4: definition of digraphs and basic properties; characterization of Eulerian digraphs 9. Sep 13, Wed. De Bruijn cycles; tournaments and kings; Sec 2.1: trees; basic definitions; lemma for induction; equivalent characterizations 10. Sep 15, Fri. basic properties of trees; spanning trees; min degree cond to force a tree as a subgraph; distance and diameter 11. Sep 18, Mon. eccentricity, radius, and center; center of a tree; Sec 2.2: Cayley's formula; Prufer codes 12. Sep 20, Wed. recursion for number of spanning trees; Matrix Tree Thm; decomposition conj 13. Sep 22, Fri. graceful labelings; graceful labelings for all trees implies decomposition conj; Sec 2.3: minimum weight spanning trees; Kruskal alg and proof; Prim alg 14. Sep 25, Mon. Chinese Postman Problem; Sec 3.1: matchings; alternating and augmenting paths; symmetric difference; Hall's condition 15. Sep 27, Wed. proof of Hall Thm; Test 1 Sept 27, Wed, 7-9pm in 341 Altgeld Sep 29, Fri. No lecture 16. Oct 2, Mon. Lemma 21; min edge covers; Gallai Thm; Konig's other Thm; Sec 3.2: maximum bipartite matching alg; proof of correctness 17. Oct 4, Wed. proof of correctness for maximum bipartite matching alg; maximum weighted bipartite matching; dual problem: vertex cover Oct 6, Fri. No lecture 18. Oct 9, Mon. more on maximum weighted bipartite matching; stable matchings: def and algorithm 19. Oct 11, Wed. stable matchings: proof of correctness; Sec 3.3: Tutte's 1-factor thm 20. Oct 13, Fri. Berge-Tutte thm; Petersen thm; thm on 2-factors; Sec 4.1: connectivity 21. Oct 16, Mon. Harary graphs; edge connectivity; edge cuts; kappa <= kappa'; 3-regular graphs 22. Oct 18, Wed. edge cuts when kappa' is small; bonds; blocks; Sec 4.2: 2-connected graphs; Whitney thm; subdivision 23. Oct 20, Fri. expansion lemma; ear decomposition; 2-edge-connected graphs; closed ear decomposition; connectivity for digraphs; Robbins thm 24. Oct 23, Mon. Menger thm; different forms 25. Oct 25, Wed. global version of Menger thm; edge and digraph versions; Sec 4.3: network flows; definitions; f-augmenting paths Test 2 Oct 25, Wed, 7-9pm in 341 Altgeld 26. Oct 27, Fri. edge cuts; weak duality; Ford-Fulkerson algorithm; correctness and finiteness; strong duality; directed edge Menger thm from Max Flow-Min Cut thm 27. Oct 30, Mon. Max Flow-Min Cut from directed edge Menger thm; baseball application; Sec 5.1: coloring; definition and examples; bounds with clique number and independence number 28. Nov 1, Wed. Mycielski construction; Cartesian products; greedy coloring 29. Nov 3, Fri. k-critical graphs; Szekeres-Wilf thm; Gallai-Roy-Hasse-Vitaver thm; Brooks thm 30. Nov 6, Mon. proof of Brooks thm; Sec 5.2: more on k-critical graphs; size of edge cuts 31. Nov 8, Wed. edge-connectivity of k-critical graphs; S-lobes; subdivisions; Dirac thm; Hajos conjecture; Hadwiger conjecture 32. Nov 10, Fri. k-chromatic and r-partite graphs; Turan thm; Sec 5.3: simplicial vertices; simplicial elimination orders; chordal graphs 33. Nov 13, Mon. equivalence of chordal and simplicial elimination orders; perfect graphs; chordal graphs are perfect; Sec 6.1: planar graphs and plane graphs; K3,3 is not planar 34. Nov 15, Wed. planar duals; outerplanar graphs; Euler's formula; edge bound 35. Nov 17, Fri. embedding on the sphere; Platonic solids; Sec 6.2: Kuratowski thm; first part of proof for low connectivity Nov 20, Mon. -- Nov 24, Fri. Thanksgiving break - no class 36. Nov 27, Mon. finished proof of Kuratowski thm; case when 3-connected; convex embeddings 37. Nov 29, Wed. 6 color thm; 5 color thm; 4 color thm; embedding graphs on surfaces of higher genus; Heawood formula; Sec 7.1: edge coloring; chromatic index; line graphs Test 3 Nov 29, Wed, 7-9pm in 341 Altgeld 38. Dec 1, Fri. edge-coloring bipartite graphs; Vizing thm; fat triangle; Shannon thm 39. Dec 4, Mon. Sec 7.2: Hamiltonian cycles; basic necessary conditions; Dirac thm; Ore thm; closure operator; Chvatal thm on degrees 40. Dec 6, Wed. Chvatal-Erdos thm; Sec 7.3: statement of Tait and Grinberg thms; Tutte's graph and proof; evaluations Dec 8, Fri. No lecture Dec 12, Tues., 7-10pm Final Exam