Math 38 - Graph Thepry - Dartmouth College

General Info | Day-to-day

Learning TeX: 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 use TikZ for pictures; 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). I also have a samle TeX file on my teaching page.

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.
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)
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
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
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

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
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
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.
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.
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

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.
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)
	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
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
	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
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
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
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.
	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.
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)