Discrete Mathematics and Graphs: Counting, Relations and Networks

Calculus studies quantities that vary smoothly. 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, and it is a very good place to learn proof.

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?" Answering them needs counting, relations, induction and graphs. Proof habits from Proof and Precise Reasoning: From Arguments to Theorems are practised here, and the A Map of Mathematics: Twenty-Five Areas and What Depends on What shows where this branch sits.

Topic order

A sensible order:

1. Logic and sets (union, intersection, complement, power sets).
2. Relations and functions.
3. Counting.
4. Induction and recurrences.
5. Graphs and trees.

Later topics (number theory, generating functions, deeper graph theory) depend on these. Counting in particular is the foundation of probability, as seen in Mathematics for Better Decisions.

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 unordered pair was counted twice, so there are 20 / 2 = 10 pairs, which 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?" and dividing by the right symmetry factor.

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

Induction and recurrences

Induction proves a statement for all natural numbers from a base case and a step. To show 1 + 2 + ... + n = n(n + 1)/2: the base case n = 1 gives 1 = 1; if it holds for n, then adding n + 1 gives n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2, which 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 terms, and 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. Key ideas:

• 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 exists between every pair, and which single vertex or edge removal would disconnect 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 the discovered distance at each step.
• Centrality. Measures such as degree or betweenness quantify which vertices matter most.

The six-degrees question belongs here. Milgram's 1967 letter-forwarding study suggested short chains between strangers, and Watts and Strogatz (1998) showed that a few random shortcuts in a mostly local network sharply cut average path length. Milgram's evidence was limited, since many chains never completed, so treat "six degrees" as a suggestive finding, not a law.

Euler's 1736 solution of the Konigsberg bridge problem is the traditional start of graph theory: a walk crossing each edge exactly once exists only if the graph is connected and zero or two vertices have odd degree.

Algorithm output versus proof

Demonstrated (the failure with negative weights can be shown by a small counterexample). 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, so a test that happens to pass proves nothing about the general case. A learner should be able to state what an algorithm computes, give an invariant that explains why it works, and reason about cost (how running time grows with input size) using complexity notation as in CLRS.

The same discipline applies to databases. A query planner estimates the cost of different join orders and index uses. Compare plans before and after adding an index using the PostgreSQL EXPLAIN documentation, and remember that an estimate is a model of cost, not the measured time.

Relational algebra and data modelling

Codd (1970) proposed modelling data as relations, with operations such as selection, projection and join. Practical lessons:

• A key identifies a row uniquely; a foreign key points to another table's key.
• Normalization removes redundancy so 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.

Graph versus network

A mathematical graph is an abstraction. A physical network has cables, delays and failures that the graph leaves out, and choosing which of these to model is a design decision. Do not confuse network topology (how nodes connect) with topological spaces in mathematics, which is a different field using a similar word. For how structure shapes behaviour, see Systems Thinking: Feedback, Queues, Information and Dynamics and Systems, Decisions and Robust Design.

Graph theory proper

With basics secure, graph theory proper covers matchings, network flows (the max-flow min-cut theorem), planarity (Kuratowski, 1930) and colouring. The Four Colour Theorem was proved with extensive computer assistance by Appel and Haken in 1976-77; it is accepted, but the original proof is not checkable by hand (a formal computer-verified proof was later completed by Gonthier in 2005, described in the 2008 reference above), an interesting case for Technology, AI and Human Judgment. Diestel's text is the standard rigorous treatment.

Practice artifacts

Mathematics is learned by making things. One suggested set: 20 explained problems across counting, relations, recurrences and graphs; one small graph model; and one normalized schema with every key and constraint explained. These feed a larger project method in Twelve-Week Arcs and the Capstone Project Method. Good texts are Lehman, Leighton and Meyer (free) and CLRS.

Try this

1. Count the handshakes among 8 people three ways: by listing, by C(8, 2), and by induction on adding a person.
2. Draw a small graph of six nodes, run breadth-first search by hand, and then write one sentence on why the distances found are shortest.
3. Design two tables, one of stable device facts and one of timestamped measurements, and say what breaks if you merge them.

Further reading

• Lehman, Leighton and Meyer, Mathematics for Computer Science (MIT OpenCourseWare).
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 4th ed.
• Reinhard Diestel, Graph Theory, 5th ed.
• E. F. Codd, "A relational model of data for large shared data banks," CACM 13(6), 1970.
• Watts and Strogatz, "Collective dynamics of small-world networks," Nature 393, 1998.