Graph Theory Math 852 Spring 2008 Section 001 Class Log

1. Jan 14, Mon. course overview and logistics; Sec 1.1: definition of graph; isomorphism; subgraph; using graphs to model problems; Konigsberg bridge problem
2. Jan 16, Wed. Petersen graph; girth; Sec 1.2: walks, trails, paths; characterization of bipartite graphs
3. Jan 18, Fri. unions of bipartite graphs; characterization of Eulerian graphs; 2 proofs: inductive and extremal; Sec 1.3: degree sum formula ("handshaking lemma")
Jan 21, Mon. No lecture
4. Jan 23, Wed. drawing with one stroke of a pencil; extremal problems; edges in connected graphs; max size of bipartite subgraph; Mantel Thm
5. Jan 25, Fri. graphic sequences; Havel-Hakimi Thm; Berge Thm; Sec 1.4: digraphs; in and out degrees; strongly and weakly connected; Eulerian digraphs
Jan 28, Mon. No lecture
6. Jan 30, Wed. guest lecturer Jamie Radcliffe; Sec 2.1: trees; characterization
7. Feb 1, Fri. Sec 1.4: De Bruijn cycles; tournaments; kings; distance, eccentricity, diameter, radius, and center
8. Feb 4, Mon. centers of trees; Sec 2.2: Cayley's formula; functional proof
9. Feb 6, Wed. guest lecturer Jamie Radcliffe; Sec 2.3: minimum weight spanning trees; algorithms
10. Feb 8, Fri. finished MWST; Sec 2.2: counting spanning trees; recurrence; Matrix Tree thm; proof by induction
11. Feb 11, Mon. orig proof ideas of Matrix Tree thm; Sec 2.1: Ringel conj; graceful labeling; Rosa thm; Sec 2.3: Chinese postman problem; can compute distances
12. Feb 13, Wed. Sec 3.1: matchings; maximum vs maximal; M-alternating and M-augmenting paths; Berge thm; Hall thm
13. Feb 15, Fri. matchings and vertex covers; Konig-Egevary thm; independent sets, matchings, vertex covers, edge covers; alpha+beta=n
14. Feb 18, Mon. Gallai thm; Sec 3.2: algo for maximum matching in bipartite graph; introduced max weighted bipartite matching
15. Feb 20, Wed. max weighted bipartite matching; min weighted vertex cover; connection to linear programming; Hungarian algorithm
16. Feb 22, Fri. example of Hungarian algorithm; stable matchings
17. Feb 25, Mon. Sec 3.3: Tutte's condition; Tutte 1-factor thm; Berge-Tutte formula
Feb 26, Tue. 6-8pm, 112 Avery Hall. Test 1
18. Feb 27, Wed. discussion of test format; proof of Berge-Tutte formula; proof by transformation; Tutte's f-factor thm
19. Feb 29, Fri. 2-factors; Petersen thm; general description of blossom algorithm
20. Mar 3, Mon. Sec 4.1: definitions of connectivity and edge connectivity; relation to minimum degree; Harary graphs; inequality between vertex connectivity and vertex connectivity
21. Mar 5, Wed. small edge cuts can't separate small sets; bonds; blocks; Sec 4.2: in 2-connected graphs, have 2 internally disjoint u,v-paths; equivalent statements
22. Mar 7, Fri. subdivision; expansion lemma; ear decomposition; 2-edge-connectivity; connectivity in digraphs; Robbins thm
23. Mar 10, Mon. Menger thm; global version
24. Mar 12, Wed. edge and digraph versions of Menger thm; Sec 4.3: network flows; f-augmenting paths; cuts; weak duality
25. Mar 14, Fri. Ford-Fulkerson alg; Max Flow-Min Cut thm; application to Menger thms
Mar 17–21. Spring break—no lectures
26. Mar 24, Mon. Sec 5.1: coloring; chromatic number; two motivating examples: map coloring and scheduling; basic bounds; greedy coloring and orders; interval graphs
27. Mar 26, Wed. greedy coloring of interval graphs; Brooks thm
28. Mar 28, Fri. Mycielski construction; Sec 8.5: probabilistic method; Szele thm
29. Mar 31, Mon. Caro-Wei thm; dominating sets; problem with proving Alon thm using First Moment Method
30. Apr 2, Wed. alteration or deletion method; Alon thm; Erdos thm
31. Apr 4, Fri. finish Erdos thm; k-critical graphs; Szekeres-Wilf thm; degrees in k-critical graphs
32. Apr 7, Mon. edge connectivity of k-critical graphs; cutsets in k-critical graphs; Dirac thm; Hajos conj
33. Apr 9, Wed. Hadwiger conj; extremal graph theory; Turan thm
34. Apr 11, Fri. alternate proof of Turan; Sec 6.1: plane drawings; planar graphs; dual graph
35. Apr 14, Mon. properties of the dual graph; Euler formula; number of edges in simple planar graphs; Platonic solids
36. Apr 16, Wed. Sec 6.2: Kuratowski thm; proof
37. Apr 18, Fri. No lecture
38. Apr 21, Mon. finished proof of Kuratowski thm; Graph Minor Thm; forbidden minors for higher genus surfaces
39. Apr 23, Wed. Sec 6.3: coloring planar graphs; Six Color thm; Five Color thm; graphs on surfaces of higher genus; Heawood formula
40. Apr 25, Fri. Sec 7.1: edge-chromatic number; relation to perfect matchings; bipartite graphs; Vizing thm
41. Apr 28, Mon. proof of Vizing thm; comparison of edge and vertex parameters Sec 7.2: Hamiltonian cycles
42. Apr 30, Wed. Dirac thm; Ore thm; Bondy-Chvatal closure; Chvatal thm
43. May 1, Fri. Sec 7.2: approach to Four Color Thm using Hamiltonicity; Tait thm; Grinberg thm; Tutte graph

    Back This page last modified .