A complete introduction to Graph Theory: from the Bridges of Königsberg to
directed graphs. Learn the mathematics behind the networks, algorithms and
connections of the digital world: degree, isomorphism, paths, trees, planarity
and more.
The articles are listed below, in the order they were written.
In 1736, Euler solved a puzzle about the bridges of a Prussian city and, without meaning to, founded graph theory. This series of 9 articles goes from the basic definitions to Kuratowski’s Theorem, through paths, trees, planarity, and directed graphs.
Can you cross the seven bridges of Königsberg passing over each one exactly once? Euler showed you can’t, and in doing so created graph theory. We will see what a graph is, the Four Color Theorem, and the computation of PageRank on a mini-web of five pages, in Python.
The formal vocabulary of graph theory: vertices, edges, neighborhood, isolated and universal vertices, complement, induced and spanning subgraphs, complete and null graphs, cliques and independent sets, with 14 worked examples and exercises.
The sum of the degrees of a graph is always twice the number of edges: this is the Handshaking Theorem. We will see degree, regular graphs, and the degree sequence, and we check the theorem on Zachary’s Karate Club, a real network of 34 people that split in two.
Two graphs with the same number of vertices, the same number of edges and the same degree sequence may not be isomorphic. We will see what isomorphism is, how to prove it with a bijection, and how to represent graphs by adjacency and incidence matrices.
How do we know whether two points of a network are connected, and by which shortest path? We define walk, trail, path, and cycle, connectivity and distance, compute distances with breadth-first search and Dijkstra, and prove that a graph is bipartite if and only if it has no odd cycle.
A file system is a tree: a connected graph with no cycles. We prove that every tree has one edge fewer than it has vertices and that its center has one or two vertices, and we look at spanning trees and rooted trees, including the difference between a balanced tree and a degenerate one.
Traversing each edge exactly once is easy to decide: just look at the parity of the degrees (Euler’s Theorem). Deciding whether we can visit each vertex exactly once is NP-complete. We will see both problems, the theorems of Dirac and Ore, and the Traveling Salesman, from Held-Karp to Christofides.
Try to connect three houses to gas, water, and electricity without crossing lines: it is impossible. We will see why, with Euler’s Formula, the proof that the three-houses graph and the complete graph on five vertices are not planar, Kuratowski’s Theorem, and the coloring of planar graphs, from six colors down to four.
A one-way street, a hyperlink, and a dependency between tasks are relations with a direction, and directed graphs exist for them. We will see in- and out-degrees, strong, unilateral, and weak connectivity, matrices, DAGs, and the topological sort that Apache Airflow uses.
