Graph theory (Math 1230)
Undergraduate course, Brown University, 2021
Course summary
This is an undergraduate course in the study of graphs. Graphs appear all over the place: both in pure and applied mathematics as well as other sciences, such as chemistry, physics, computer science, and linguistics. We will focus on the theoretical aspects of graph theory, although we will also discuss some applications.
Some highlights of what we’ll learn in this course:
- basic properties of graphs (bipartite, Eulerian, matchings, connectivity, colorability, planarity)
- classical theorems about graphs (e.g. Hall’s matching theorem, max-flow/min-cut)
- classical algorithms about graphs (e.g. Gale-Shapely proposal algorithm)
- theoretical trends in graph theory (TONCAS, dual problems, extremal problems, spectral theory)
- applications of graph theory (4-color theorem, applications of Ramsey theory)
- how to read/write proofs and critique arguments
Textbook
West, Introduction to graph theory
Topic schedule
- Week 1: Introduction
- Thurs (1/21). Definition/examples, vertex degrees, subgraphs, isomorphism
- Week 2: Introduction/Connected graphs and trees
- Tues (1/26). Bipartite graphs, bridges of Konigsberg
- Thurs (1/28). Eulerian graphs, Connected graphs and trees
- Fri (1/29). HW1 due.
- Week 3: Trees
- Tues (2/2). Characterization of trees, counting trees with n vertices
- Thurs (2/4). Cayley’s formula and Prufer codes, spanning trees
- Fri (2/5). HW2 due
- Week 4: Matchings
- Tues (2/9). Matchings, Hall’s theorem, Maximum matchings
- Thurs (2/11). Maximum matchings, proof of Hall’s theorem
- Fri (2/12). HW3 due
- Week 5: Matchings
- Tues (2/16). No class (university holiday).
- Thurs (2/18). Konig’s theorem, Gale-Shapely algorithm
- Fri (2/19). HW4 due
- Week 6: Matchings/Midterm
- Tues (2/23). proof of Konig’s theorem, analysis of Gale-Shapely
- Thurs (2/25). No class (midterm)
- Fri (2/26). Take-home midterm due at 5pm.
- Week 7: Connectivity
- Tues (3/2). Connectivity, vertex cuts, 2-connected graphs, Menger’s theorem
- Thurs (3/4). Menger’s theorem, flows, max-flow/min-cut
- Fri (3/5). HW5 due
- Week 8: Graph Coloring
- Tues (3/9). Graph coloring, Brook’s theorem, Mycielski construction, critical graphs
- Thurs (3/11). Chromatic number of critical graphs, extremal problems, Turan graphs
- Fri (3/12). HW6 due
- Week 9: Ramsey theory
- Tues (3/16). Ramsey numbers, Ramsey’s theorem, arithmetic progressions, random knots
- Thurs (3/18). Probabilistic method, Ramsey theory and Fermat’s last theorem
- Fri (3/19). HW7 due
- Week 10: Graphs and topology
- Tues (3/23). planar graphs, Jordan curves, Euler’s formula, Kuratowski’s theorem
- Thurs (3/25). Fary’s theorem, 6-color theorem
- Fri (3/26). HW8 due
- Week 11: Spectral graph theory
- Tues (3/30). Graph Laplacian, λ_1 and connectedness, Matrix-Tree theorem
- Thurs (4/1). λ_n and bipartite graphs, Matrix-Tree theorem
- Fri (4/2). HW9 due
- Week 12: Final project presentations
- Nick and Joanna: Cayley graphs
- Liang, Caleb, Seiji: the Hadwiger-Nelson problem
- Qianfan and Ruixiang: Rado’s random graph
- Elliott, Jason, Viola: the graceful tree conjecture
- Robert, Ethan, Eli: Ford-Fulkerson and sports elimination
- Paul and Ben: the Dinitz theorem
- Week 13: Final project presentations
- Cole: relative neighborhood graphs
- Enrique: single-minded auctions
- Dhruv and Richard: perfect matchings in infinite graphs
- Romina, Timothy, Jacob: the art gallery problem
- Sameerah and Arturo: the 5-color theorem
- Sreshtaa, Lily, Ryan: de Bruijn graphs and genome sequencing
- David, Ken, Petar: the stable roommates problem
Homework assignments
HW1 HW2 HW3 HW4 HW5 HW6 HW7 HW8 HW9