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

    Back This page last modified .