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.
What is the coefficient of a term in the expansion of a binomial raised to the tenth power? The binomial theorem answers in one line, with the coefficients from Pascal’s triangle. We will see the theorem and its proof by induction, the general term formula, and the identities that come from special cases.
A set with 10 elements has 1,024 subsets, and that is the sum of row 10 of Pascal’s triangle. We will see the identities of binomial coefficients: symmetry, Pascal’s rule (Stifel’s rule), and the row, column, and diagonal theorems.
At an ice cream shop with 7 flavors, there are 210 ways to order 4 scoops, repeating flavors allowed. We get there with the stars and bars method, which shows that choosing with repetition, distributing balls into boxes, and solving integer equations are the same problem.
A 4-digit password allows repetition, and that is why there are 10,000 of them: ten options in each of the four positions. The arrangement with repetition counts passwords, license plates, and RGB colors, and shows how many patterns fit in the 32 bits of a float and in the registers of an HP-11C calculator.
How many anagrams does the word MAMBEMBE have? Fewer than an 8-letter word with distinct letters would have, because swapping two equal letters does not create a new anagram. The formula discounts the repetitions by dividing by factorials, and it works for binary sequences and for shortest paths on grids.
Out of 10 friends, 3 go buy the popcorn. Only who goes matters, not the order of the choice, so there are 120 possible groups. We will see the combination formula, its symmetry, the complement method, and how to split a set into groups.
In a race with 10 athletes, the podium can be filled in 720 ways. That is an arrangement, an ordered selection of some elements of a set. We solve problems about routes, license plates, and numbers with distinct digits, with Python and SQL.
How many anagrams does the word VIRUS have? In how many ways can 5 friends sit around a table? The answers are 120 and 24, by simple and circular permutations. We will also see adjacency restrictions, the traveling salesman problem, and derangements.
With 4 math books and 3 Portuguese books, there are 7 ways to pick one book and 12 ways to pick one of each. The first count is a sum and the second is a product: these are the sum rule and the product rule, applied here to passwords, flags, answer keys, and counting divisors.
How many 8-character passwords are there? In how many ways can 10 people sit around a table? Combinatorics answers without listing every case. This is the roadmap of the series: from the counting rules to permutations, arrangements, combinations and the binomial theorem.
How many moves does it take to solve the Tower of Hanoi? The answer comes from a recurrence relation, which writes the problem in terms of itself with one disk fewer. We set up recurrences and solve them by substitution, by the characteristic equation and by the Master Theorem, used for merge sort.
What if the step depends on more than one earlier case, as in Fibonacci? Strong induction assumes all the earlier cases. We will see the technique at work on prime factorization, the chocolate bar, postage stamps and Binet’s formula, which in floating point fails from the 71st term on.
If the first domino falls and each domino knocks over the next, they all fall. That is the logic of the Principle of Mathematical Induction. We will see the structure of the proof (base case, hypothesis and step) in sums, divisibility and inequalities, and the false proof that all horses are the same color.
How do you prove a formula holds for every natural number, if there are infinitely many of them? With mathematical induction. This introduction maps out the series: classic induction, strong induction and recurrence relations, from Fibonacci to the Tower of Hanoi.
Adding the sizes of two sets counts the intersection twice. The Inclusion-Exclusion Principle fixes the count, for two, three, or any number of sets. We will also see infinities of different sizes, derangements, and the Sieve of Eratosthenes.
Union, intersection, difference, and complement are the basic operations on sets, and they show up in SQL as UNION, INTERSECT, and EXCEPT. We see each one in Venn diagrams, along with De Morgan’s laws, distributivity, and the difference between a Venn diagram and an Euler diagram.
The collection of tall people is not a set: there is no criterion that decides, for any person, whether they belong or not. We define set, membership, roster and set-builder descriptions, equality, inclusion, and the power set.
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.
