Spring 2005 Math 412 Graph Theory Class Log

Class Log

1. Jan 19, Wed. course overview and logistics; Sec 1.1: definition of graph; Konigsberg bridge problem; graphs as models: acquaintance relations, job assignment, scheduling, coloring
2. Jan 21, Fri. subgraphs; isomorphism; decomposition and self-complementary graphs; Petersen graph and its girth
3. Jan 24, Mon. adjacency and incidence matrices; Sec 1.2: walks, trails, and paths; connected graphs; components; cut-vertices and cut-edges; characterization of bipartite graphs
4. Jan 26, Wed. K_n as the union of bipartite graphs; characterization of Eulerian graphs
5. Jan 28, Fri. extremality and alternate proof for characterization of Eulerian graphs; drawing graphs with continuous segments; Sec 1.3: degrees and counting; definition of hypercube; extremal problems and sharpness; min number of edges in a connected graph; bound on min degree to ensure connectedness
6. Jan 30, Mon. large bipartite subgraphs; Mantel Thm; induction trap; degree sequences realizable by a multigraph
7. Feb 2, Wed. graphic sequences; Havel-Hakimi Thm; Berge's 2-swap Thm; Sec 1.4: digraphs and basic properties
8. Feb 4, Fri. Eulerian digraphs; De Bruijn cycles; tournaments and kings; games and kernels of digraphs
9. Feb 7, Mon. Sec 2.1: trees and basic properties; characterizations; forcing a tree as a subgraph
10. Feb 9, Wed. distance, diameter, and radius; Thm 11; center of a tree; Wiener index; maximum and minimum fro trees and graphs; winning strategy in Bridg-It
11. Feb 11, Fri. Sec 2.2: Cayley's formula; Prüfer codes; trees with given degrees; counting the number of spanning trees of a graph by recurrence
12. Feb 14, Mon. Matrix Tree Theorem; decomposition into trees; graceful labelings; Sec 2.3: weighted graphs; minimum weight spanning trees
13. Feb 16, Wed. Kruskal's algorithm; shortest paths and Dijkstra's algorithm; Chinese Postman Problem
14. Feb 18, Fri. Sec 3.1: matchings; augmenting and alternating paths; Hall Thm
15. Feb 21, Mon. Marriage Thm; min-max theorems; Konig-Egervary Thm; Gallai Thm
16. Feb 23, Wed. Konig's Other Thm; Sec 3.2: maximum bipartite matching algorithm and proof; Hungarian algorithm for maximum weighted bipartite matching
17. Feb 25, Fri. Proof of Hungarian algorithm; stable matchings and Gale-Shapley Alg
18. Feb 28, Mon. analysis of Gale-Shapley Alg; Sec 3.1: 1-factors; Tutte's 1-factor Thm; Berge-Tutte formula
19. Mar 2, Wed. Petersen's Thm on 3 regular graphs; 2-factors in graphs with positive even degree; Sec 3.1: separating sets, connectivity, k-connected; Harary graphs
20. Mar 4, Fri. disconnecting sets, edge cuts, edge connectivity; Whitney's Thm relating connectivity, edge connectivity and minimum degree; Cor 13: size of S for small edge cuts; bonds; Prop 15: characterizing a bond F in terms of number of components of G-F; blocks; block-cutpoint graph is a trees
21. Mar 7, Mon. Sec 4.2: 2-connected graphs; Whitney Thm; characterization; subdivisions; ear decomposition; 2-edge-connected graphs; closed ear decomposition; Robbins Thm
22. Mar 9, Wed. Menger Thm; different forms
23. Mar 11, Fri. applications of Menger Thm; Sec 4.3: network flows; duality with edge cuts
24. Mar 14, Mon. f-augmenting paths; Ford-Fulkerson algorithm; Max-flow Min-cut Thm; Integrality Thm; equivalence with Menger's Thm
25. Mar 16, Wed. baseball application; Sec 5.1: coloring, basic definitions and concepts
26. Mar 18, Fri. box product; greedy coloring; k-degenerate graphs; Szekeres-Wilf thm; interval graphs
Mar 21, Mon. -- Mar 25, Fri. Spring break, no lectures.
27. Mar 28, Mon. Gallai-Roy-Vitaver-Hasse Thm; Brooks Thm; Sec 5.2: Mycielski construction
28. Mar 30, Wed. extremal number of edges in a k-chromatic graph; Turan Thm
29. Apr 1, Fri. color-critical graphs; edge-connectivity of color critical graphs; K_4 subdivisions in 4-chromatic graphs
30. Apr 4, Mon. Sec 5.3: chromatic polynomial of a graph; methods of calculating
31. Apr 6, Wed. chordal graphs and simplicial elimination orderings; perfect graphs
32. Apr 8, Fri. Sec 6.1: planar graphs; K_5 and K_{3,3}; dual; cycles vs bonds; bipartite planar graphs
33. Apr 11, Mon. outerplanar graphs; Euler's formula; edge bound; Platonic solids
34. Apr 13, Wed. Sec 6.2: Kuratowski Thm
35. Apr 15, Fri. Sec 6.3: planarity testing algorithm; coloring of planar graphs; 6 Color Thm; 5 Color Thm
36. Apr 18, Mon. ideas of 4 Color Thm; crossing number; crossing number of K_n; embedding on surfaces of higher genus
37. Apr 20, Wed. Sec 7.1: line graphs; edge coloring; edge coloring of bipartite graphs
38. Apr 22, Fri. Vizing Thm
39. Apr 25, Mon. Sec 7.2: hamiltonian cycles; necessary condition; Dirac Thm; Ore Thm; closure
40. Apr 27, Wed. Chvatal condition; Chvatal-Erdős Thm
41. Apr 29, Fri. Sec 7.3: Tait Thm; Grinberg Thm
42. May 2, Mon. optional lecture
43. May 4, Wed. optional lecture

    Back This page last modified .