Graph Theory — Between the Lines
From the definition of a graph to matroids. An eight-part series that answers the questions textbooks leave between the lines, building intuition for graph theory.
What is a graph, really? — A tool for making relationships visible
From the bridges of Konigsberg to social networks, dependency management, and scheduling, an astonishing variety of problems reduce to graphs. This article explains the intuition behind undirected, directed, and weighted graphs, and why this abstraction is so powerful.
Why does BFS find shortest paths? — The ripple analogy
BFS finds shortest paths in unweighted graphs, but why should breadth-first exploration guarantee optimality? Using the analogy of ripples on a pond, we build intuition for the correctness of BFS, see why DFS fails, and understand Dijkstra as a generalization to variable-speed ripples.
Why are trees special? — The beauty of minimal connectivity
Seven equivalent characterizations of trees all say the same thing from different angles: a tree is a connected graph with zero redundancy. Add one edge and a cycle appears; remove one edge and the graph disconnects. This article unpacks the beauty behind that knife-edge structure.
Why does the greedy algorithm work for trees? — What matroids reveal
Kruskal's algorithm for minimum spanning trees is absurdly simple: sort the edges by weight and add the cheapest one that does not create a cycle. Why does this greedy strategy produce an optimal solution? The answer lies in the cut property and, more deeply, in matroids.
The Euler--Hamilton divide: why "all edges" and "all vertices" are worlds apart
Determining whether a graph has an Eulerian circuit (traversing every edge exactly once) reduces to checking vertex degrees. Determining whether it has a Hamiltonian cycle (visiting every vertex exactly once) is NP-complete. This article explains why one word makes all the difference.
What the max-flow min-cut theorem is really saying — Duality in action
The maximum flow through a network equals the minimum capacity of a cut separating source from sink. This elegant duality is one of the most beautiful results in combinatorics. We develop intuition through water pipes, augmenting paths, and LP duality.
The magic of bipartite graphs — Why everything works
The absence of odd cycles is a single structural property, yet it makes matching, coloring, and covering all tractable at once. This article explores the remarkable power of bipartiteness through K"onig's theorem, Hall's marriage theorem, and the reduction patterns they enable.
What does the shape of a graph determine? — From planarity to the four-color theorem
Planar graphs are sparse ($E \leq 3V - 6$), and many problems that are hard on general graphs become tractable when planarity is assumed. This article covers Euler's formula, Kuratowski's theorem, and the philosophical significance of the four-color theorem.