Discrete Mathematics and Graphs: Counting, Relations and Networks

Counting, relations, induction and graphs, held together by one discipline: count each object exactly once, and prove a result instead of sampling it.

Milgram's numbers do not balance: 44 + 126 = 170, not 160. The article does not say which is wrong, and its chart also counts 44 completed chains. Steven Strogatz, co-author of the small-world model, pointed out the sum on NPR in 2008. The 1969 journal report (Travers and Milgram) counts more cleanly: 296 starters, 217 who sent the folder on, 64 chains that arrived.

That slip is the subject in miniature. Discrete mathematics studies things you can count and separate: sets, steps, states, connections. It is the native language of computing, networks and any system built from distinct parts. It is also a very good place to learn proof. Its discipline has two halves: count each object exactly once, and prove a claim instead of sampling it.

Why discrete structure matters

Established A data structure, a network, a state machine and a schedule are all finite objects with definite parts. Their questions are "how many?", "is it connected?", "what is the cheapest way?" and "can this ever go wrong?" Proof habits from Proof and Precise Reasoning are practised here. The Map of Mathematics shows where this branch sits. A sensible order runs logic and sets, relations and functions, counting, induction, then graphs and trees. Each step leans on the ones before.

Counting without overcounting

The multiplication principle says independent choices multiply. Choosing an ordered pair from 5 people gives 5 x 4 = 20 outcomes. If order does not matter, each pair was counted twice, so there are 20 / 2 = 10 pairs. That is the binomial coefficient C(5, 2). In general C(n, k) = n! / (k!(n - k)!). The core skill is asking "did I count the same object more than once?" Then divide by the right symmetry factor. Counting is also the foundation of probability, as in Mathematics for Better Decisions.

An equivalence relation is reflexive, symmetric and transitive. It splits a set into classes with no overlap, so each element lands in exactly one class. Congruence modulo n is the standard example: 3 and 8 are in the same class modulo 5. Proving the three properties is a good first exercise.

Induction and recurrences

Checking cases is sampling. Induction proves a statement for all natural numbers from a base case and a step. To show 1 + 2 + ... + n = n(n + 1)/2, start with n = 1, which gives 1 = 1. If the formula holds for n, adding n + 1 gives n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2. That is the formula for n + 1. A recurrence, such as the Fibonacci rule F(n) = F(n - 1) + F(n - 2), defines terms from earlier ones. Induction is the natural tool for proving facts about it.

Graph basics

A graph is a set of vertices and a set of edges joining pairs of them.

Paths and cycles. A path never repeats a vertex; a cycle returns to its start.
Trees. A connected graph with no cycles. A tree on n vertices has exactly n - 1 edges, a fact provable by induction.
Connectivity. Whether a path joins every pair, and which single vertex or edge removal would split the graph.
Traversal. Breadth-first search explores in rings of distance from a start vertex, using a queue. Trace one by hand: list the queue, the visited set and each distance found.

The six-degrees question belongs here. Watts and Strogatz (1998) showed that a few random shortcuts in a mostly local network sharply cut average path length. That makes short chains plausible. Milgram's evidence was thinner: most chains never finished. Treat "six degrees" as a suggestive finding, not a law.

A proof can also arrive in halves. Euler's paper on the Königsberg bridges (written 1735, published 1741) is the traditional start of graph theory. A walk crossing each edge exactly once exists if and only if two things hold. All the edges lie in one connected piece (isolated vertices do not matter), and zero or two vertices have odd degree. Euler showed these conditions are necessary. Hierholzer's proof that they are also sufficient was published in 1873. That split is the standard account, not checked here against the papers.

Algorithm output versus proof

Demonstrated Running an algorithm on an example gives a result. It does not show that the algorithm is correct. Dijkstra's shortest-path algorithm returns correct answers when edge weights are non-negative, and a proof by an invariant shows it. With negative weights it can fail. Take four one-way edges: S to A costs 2, S to B costs 4, B to A costs -3, A to C costs 1. Dijkstra settles A at 2, then C at 3, then B at 4. That is too late. S to B to A to C costs 4 - 3 + 1 = 2, but C keeps its distance of 3. So a test that happens to pass proves nothing about the general case.

Learn to state what an algorithm computes and give an invariant that explains why it works. Then estimate how its running time grows with input size, as in Cormen and colleagues' Introduction to Algorithms.

The Four Colour Theorem shows the other side. Appel and Haken's 1977 proof leaned on extensive computer checking, and the original is not checkable by hand. Gonthier later completed a formal, computer-verified proof (described in his 2008 paper). Who checks the checker is a question for Technology, AI and Human Judgment.

Store each fact once

Codd (1970) proposed modelling data as relations, with operations such as selection, projection and join. A key identifies a row uniquely. Normalisation is counting discipline for data: each fact is stored once. Separate stable facts (a device's model) from changing observations (a reading at a time), so that new measurements append rather than overwrite history. This is the same distinction as in Stale Information and Dependable Reports: a stored value is a claim about a moment in time.

To consolidate, build 20 explained problems, one small graph model and one normalised schema. Twelve-Week Arcs and the Capstone Project Method turns such pieces into a larger project.

Where this could be wrong

Strongest objection. Working engineers rarely prove their algorithms. They test, and tests catch most bugs in practice. Insisting on proof can look like a classroom habit.

Best reply. Tests and proofs answer different questions. A test says this input worked. A proof says no input within its assumptions can fail. The four-edge example shows how tests can miss a whole class of inputs.

What would settle it. Evidence on whether learners who write invariants catch more boundary failures, such as negative weights, than learners who only test. This page has not checked such evidence, so the emphasis is Provisional.

Try this

Count the handshakes among 8 people three ways: by listing, by C(8, 2), and by induction on adding a person.
Draw a small graph of six nodes and run breadth-first search by hand. Then write one sentence on why the distances found are shortest.
Design two tables, one of stable device facts and one of timestamped measurements. Say what breaks if you merge them.
Find Milgram's slip. List two ways the 160, 44 and 126 could be reconciled, and say what record would decide between them.