Vineeth Chintala

Intro to Graph Theory

I taught intro courses on graph theory at IISc (in 2024 and 2025). During this time, I was also working on my book - Graphs, Games, Algorithms. In 2020-21, I spent a year teaching Linear Algebra, Graphs and Algorithms at the University of Hyderabad.

Graphs, Games, Algorithms Book Cover

Graphs, Games, Algorithms

Free eBook  •  Amazon (US)
The book is extremely modular so read the chapters that appeal to you first. The book has four parts:

Better Way: uses puzzles to introduce core principles
Way Better: covers classic algorithms
The Unreasonable Power of Linear Algebra: showcases algebraic techniques
Senses of a Graph: surveys major 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

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

  3. Specialized topics:
    Two sided matching - Roth, Sotomayer
    The game of cops and robbers on Graphs - Bonato, Nowakowski

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

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

  6. A list of famous algorithms:
    https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book

  7. 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
    Judy Swan: https://youtu.be/jLPCdDp_LE0