Fall 2004 Math 412 Graph Theory sections G1U and G1G

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

    Back This page last modified .