Intro to Graph Theory
Intro to Graph Theory
I will be teaching MA 216 : Introduction to Graph theory during the Jan-April 2025 semester (at IISc, Bangalore). I have also taught this course in 2024 and have written an introductory book on graph theory. The book and course will have roughly 80-90% intersection, so check out the preface/contents for a detailed description.
Updates:
June, 2025: The book has been completed! I have added many diagrams to accompany the proofs. Comments and feedback are welcome.
Description: Some of the special chapters are called ``gems from grad school". These are beautiful results discovered by people while they were graduate students. Maybe one of these stories will inspire you too. Who knows where the next big idea will come from!
The book is extremely modular so read the chapters that appeal to you first.
Part 1 (Better way) introduces some of the concepts using puzzles
Part 2 (Way better) covers algorithms
Part 3 (Many senses of a graph) surveys some of the themes.
This is intended to be a short fun book covering graph theory and algorithms, designed to be useful irrespective of your major. Feel free to send me feedback.
Graph theory resources
There are a lot of books and lecture notes out there, each having their own style and content - I recommend checking out and finding what suits your interests.
1. Basic to Intermediate, highly readable (where some chapters cover graph theory):
Invitation to discrete mathematics - Matousek, Nesetril
Algorithms illuminated - Roughgarden
Algorithm design - Tardos, Kleinberg
The discrete mathematical charms of Paul Erdos. - Vasek Chvatal
Some other popular textbooks are by Douglas West, Bondy and Murty, Harary, Bóna
2A. Intermediate to Advanced:
Graph theory, Diestel
Spectral and algebraic graph theory, Spielman
Also check out the following talk: Miracles in Algebraic graph theory by Spielman
https://youtu.be/CDMQR422LGM?si=Qx9Zbta4ejbeTHXo
2B. Specialized topics
Two sided matching - Roth, Sotomayer
The game of cops and robbers on Graphs - Bonato, Nowakowski
3. Advanced
The Probabilistic method - Alon, Spencer (The book for the probabilistic method)
Erdos on Graphs - Chung, Graham (contains many open problems)
Enumerative Combinatorics - Richard Stanley
4. Some resources for puzzles/gems:
Proofs from the Book - Aigner, Ziegler
33 miniatures, Matousek
Algebraic combinatorics, Stanley (there is a section called Mathematical gems)
Mathematical Puzzles- Peter Winkler
Also recommend checking out people who wrote widely (and well) on recreational mathematics - Henry Dudeney, Sam Lloyd, Martin Gardener, Ross Honsberger, Peter Winkler
5. A list of famous algorithms
https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book
6. Science Writing:
Here are a couple of engaging talks on science writing that I found extremely useful. Both cover different ground, so check them both sometime.
Larry McEnerny
https://youtu.be/vtIzMaLkCaM?si=Wr9pdsexvdFepISi
Judy Swan:
https://youtu.be/jLPCdDp_LE0?si=E6-YTx8FYEY7TdJC