Teaser - Introduction to Graph Theory

On my upcoming 5-part series on the fundamental ideas of graph theory, the most important concept in discrete math.

Hey folks!

This post is a teaser for an upcoming series on graph theory I’ll be writing in collaboration with Tivadar Danka from The Palindrome . The series aims to introduce readers to the fundamentals of graph theory, and the articles will prioritize intuition over formalism without losing rigor, presenting the key ideas —as it is a staple in both Tivadar’s and my own articles.

Why should you care?

Graph theory is essential for many practical reasons, whatever your field of expertise. Graphs are the quintessential abstract representation for a vast range of domains, from computer networks to social networks, DNA, city planning, game theory… I could go on and on.

But, if you’re just a bit like Tivadar and me, and you love math for its beauty, then graph theory is one of the most fascinating subjects for the many unintuitive and significant theorems and results.

Am I the right person to teach you this?

If you’re a long-time reader of Mostly Harmless Ideas, you already know that I love writing about the most fascinating topics in Computer Science, always from an intuitive and pragmatic perspective. You might also know that I have a Ph.D. in machine learning and do research on practical applications of language models.

What you might not know is that I’m also a full-time lecturer in a CS major, and I’m currently teaching an undergrad Discrete Math course, which is more than 60% graph theory.

As far as credentials matter —which is fairly little, to be honest— I think that covers it. What’s more important is that I’ve spent my entire career thinking about how to make CS education more approachable. So whether you’re new to all of this or already know a lot about graphs, I believe I can give you a couple novel points of view that I’m sure will surprise you.

So, now that you’re convinced, here’s the deal.

The posts will be published first in The Palindrome and then cross-posted here after the series is complete. We plan to publish one article each week starting next week and should finish around the end of the year. If you want to read them as they come out, subscribe to Tivadar!

The series is not algorithmic but theory-oriented. We will dive deep into why graphs have some of the intriguing properties they have. It’s all about the beauty of graphs rather than the pragmatics. However, in that exploration, we will build some strong intuitions that will later —in a future series on graph algorithms— help us design clever computational strategies.

Since this is a series on theory, we will do lots of proofs! However, to keep articles useful for all readers, we will do them in two layers. First, we will see all the intuitions behind each theorem, understand what it says, and why it must be true. Then, we will have an optional section for the math nerdy who wants to see the technicalities.

Ok, but what’s inside?

I'm glad you asked! Here’s a short table of the contents we have planned. We may adjust it a bit as we see how complex or long each topic gets.

1 - The Basics

• Why graphs matter, a bit of history, and some examples of applications of graphs.

• Basic concepts: vertices, edges, paths, and cycles.

• Undirected, directed, and weighted graphs.

• Connected graphs and connected components, cuts.

• Special types of graphs: complete and bipartite.

• Subgraphs, induced and spanning.

2 - Trees

• What is a tree, examples of applications of trees.

• Basic properties of trees.

• Spanning trees, what are they, and why are they useful.

• Properties of spanning trees.

• Some intuitions about finding minimum spanning trees.

3 - Matching and Bipartite Graphs

• What is matching in general and in bipartite graphs.

• Examples of matching problems.

• Properties of matching in general graphs.

• Finding a matching in general graphs (Berge’s theorem).

• Finding a matching in bipartite graphs (Hall’s theorem).

4 - Tours: Eulerian and Hamiltonian

• Why tours are important.

• Examples of problems that involve tours.

• Eulerian tours, when they exist, and how to find them.

• Hamiltonian tours, why are they hard to find.

• Sufficient conditions for Hamiltonian tours (Dirac’s theorems)

• Closures and closed characterizations of Hamiltonian tours.

5 - Drawing Graphs: Planarity and Coloring

• Examples of applications of planarity and graph coloring.

• Basic properties of planar graphs.

• When is a graph planar? (Kuratoski’s theorem)

• Why graph coloring is hard.

• Some unintuitive results about graph coloring.

• Coloring in planar graphs (the 4 colors theorem).

---

Are you ready for a deep dive into the fascinating world of graph theory? Hit that subscribe button, and I’ll be back in your inbox with the first article before you can say “induction”!