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

    Back This page last modified .