General Info | Day-to-day
Learning TeX: If you would like to learn LaTeX, I have posted solutions in both .pdf and .tex to help out. You'll need to install an editor (my favorite for Macs is TeXShop, and I've heard TeXMaker is good for other platforms). You'll also need a TeX distribution; everything is linked to from the math department's page on TeX. A good overall guide to learning LaTeX is the Not So Short Guide. I've been coding the pictures in TikZ; the manual I use for this is Till Tantau's PGF Manual, but really I learned by digging around the TikZ example database (in general, TeXample.net is awesome).
| Week 1 | 1.1, 1.2: Definitions, examples of problems in graph theory, isomorphisms. Paths, walks, cycles, components, bipartite graphs, Eulerian graphs. | |
| Due 3/30: 1.1 #10, 11, 14, 15, 25, 29. Solutions: pdf or TeX | ||
| Week 2 |
1.3, 1.4: Vertex degrees, extremal problems, degree sequences. Directed graphs, de Bruijn cycles, orientations. Slides: Hypercube for k=4, Degree sequences |
|
|
Due 4/6: 1.1 #30, 1.2 #1, 4, 12, 15, 18, 38, 42, 1.3 #9, 22 ((c) is extra credit) Solutions: pdf or TeX |
||
| Quiz Tuesday 4/10: Chapter 1. (Solutions) | ||
| Week 3 | 2.1: Trees and distance, spanning trees, radius and diameter. | |
|
Due 4/13: 1.3 #8, 18, 25, 32, 44, 63, 1.4# 8, 10, 14, 2.1 #2, 18 Template: .tex Solutions: .pdf or .tex |
||
| Week 4 |
2.2: Enumeration of trees, Cayley's formula, Prufer code. Counting spanning trees, deletion-contraction, the matrix tree theorem, graceful labelings. Pictures from class |
|
|
Due 4/20: 2.1 # 13, 40, 44, 47, 62, 68, 2.2 # 1, 8 Template: .tex Solutions: .pdf or .tex |
||
| Quiz Tuesday 4/24: Sections 2.1, 2.2. (Solutions) | ||
| Week 5 |
2.3: Minimum spanning trees (Kruskal's algorithm), shortest paths (Dijkstra's algorithm). Slides A survey article on applications for labeled graphs, and more modern A Dynamic Survey of Graph Labeling |
|
|
Due 4/27: 2.2 #3, 10, 23, 31, 33, 2.3 #2, 4, 10 Template: .tex Solutions: .tex or .pdf |
||
| Week 6 | 3.1: Matchings, Hall's theorem, min-max theorems, maximum matchings, independent sets, vertex and edge coverings. Matchings review slide [P Hall 1935] [Mirsky 1971] [M Hall 1948] [Rizzi 2000] | |
| Midterm: Chapters 1 and 2. Out Monday, in Friday. (Solutions) | ||
|
Recommended problems for 5/4: 2.3 #6, 20, 23, 24, 3.1 #2, 3, 8, 11 Solutions to 2.3 problems: .pdf |
||
| Week 7 | 4.1, 4.2: Cuts, connectivity, edge-connectivity, blocks, k-connected graphs, Menger's theorem, line graphs. | |
|
Due 5/11: 3.1 #1, 3, 9, 12, 18, 30, 42 Template: .tex Solutions: .tex or .pdf | ||
| Week 8 | 4.3: Network flow problems, max-flow min-cut theorem, Ford-Fulkerson algorithm. | |
| Quiz Tuesday 5/15: Sections 3.1, 4.1, 4.2. (Solutions) | ||
|
Due 5/18: 4.1 #1, 7, 10, 14, 20, 25; 4.2 #8, 2, 22. Solutions (skecthes from the grader): .tex or .pdf | ||
|
Reading for Friday 5/18: 4.2 pp166-170 (stop before Thm 24), 4.3 pp176-178. (We'll talk about augmenting paths) | ||
| Week 9 | 5.1, 6: Vertex colorings, bounds on chromatic numbers. Planar graphs, Euler's formula,. | |
|
Reading for Monday 5/21: 4.3 pp179-184 (stop before supplies and demands), 5.1 pp 191-193. Reading for Tuesday and Wednesday: Finish 5.1. Reading for Friday: 6.1.
| ||
|
Due 5/25: 4.2 #23, 4.3 #2, 5, 13, 5.1 # 1, 19, 31, 38 I suggest that you get through as many of the (-) problems as you have time for. Solutions (skecthes from the grader): .pdf | ||
| Week 10 | 6: Kuratowski's theorem, five and four color theorems. | |
|
Suggested problems: 6.1 # 3, 5, 11, 25, 30. | ||
| Final exam: out 5/25, due 6/2 at 2pm. (put it under my door) |
Recent posts on graph theory (and other combinatorial topics):
math.CO on arXiv
Journal of Graph Theory