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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
In how many ways can you choose a valid password? What is the shortest path between two cities? These are questions of discrete mathematics. This roadmap introduces the site’s four series on the topic: sets, induction and recurrence, combinatorics, and graphs, with 28 articles.
