Graph theory

The study of finite sets together with a relation on their pairs. A simple graph is a pair (V, E) where V is a finite set of vertices and E is a set of two-element subsets of V — that is the whole definition, and grinberg-graph-theory gives it on its ninth page.

What the definition encodes is narrow on purpose: relations that are binary, symmetric and irreflexive. Coprimality on {1, …, n} nearly fits (the graph forgets that 1 is coprime to itself); "has been married to" fits exactly. Loosening any of the three conditions gives one of the other kinds of graph, and the four kinds are why the subject's opening chapters look repetitive:

simple graph — the base case, no loops, no repeated edges;
multigraph — edges become objects with endpoints, so two vertices can be joined twice;
digraph / multidigraph — the relation stops being symmetric, and each arc has a source and a target;
tournament — a digraph in which exactly one arc runs between each pair, the model of a round-robin competition.

Grinberg converts systematically between them and calls multidigraphs "a big tent," since the other three embed in it. The cost of that generality is that most theorems get stated twice, once undirected and once directed, and the directed statement is usually the harder one. Menger's theorem gets four versions in his Chapter 10 (arc and vertex, directed and undirected).

The results a first course reaches

Almost all of these are existence or counting statements about finite objects, which is the sense in which the subject is discrete rather than analytic.

Eulerian circuits — a closed walk using every edge exactly once. Euler asked it of Königsberg's bridges in 1736 and it is the subject's origin; the Euler–Hierholzer theorem settles it by a degree condition (every vertex even, graph connected). Cheap to test.
Hamiltonian cycles — a cycle through every vertex exactly once, and the contrast case: no clean characterisation exists, only sufficient criteria (Ore, Dirac) that ask for enough edges.
Trees and spanning trees — a connected graph with no cycles; a dozen conditions turn out to be equivalent to being one (the "tree equivalence theorem"). Every connected graph contains a spanning tree, and counting them is where the algebra enters (matrix-tree-theorem).
Proper colorings — assign colors so adjacent vertices differ. Two colors are possible exactly when there is no odd cycle; Brooks bounds the general case by the maximum degree; the number of k-colorings is a polynomial in k.
Independent sets and Turán's theorem — how many edges a graph can have before it is forced to contain a complete subgraph.
Matchings — Hall's marriage theorem: a bipartite graph has a matching saturating one side exactly when no set of k vertices on that side has fewer than k neighbours. König and the Birkhoff–von Neumann theorem on doubly stochastic matrices sit beside it.
Flows — max-flow-min-cut, and then Hall derived from it, which is Grinberg's route: the combinatorial theorem falls out of the network theorem rather than the reverse.
Menger and Gallai–Milgram — how many vertex- or edge-disjoint paths connect two vertices, and how few paths cover a digraph.

Where the computing questions sit

Graph theory is the branch of mathematics computing borrows from most heavily, and the corpus's one text is careful to say it is not doing algorithms. It still draws one line sharply: asking for a shortest path between two vertices is easy (polynomial), asking for a path of a given length is NP-hard. Same objects, same graph, one word apart. The tractable question has a recursion on walk length behind it; the hard one is not expected to have anything.

Adjacency and Laplacian matrices are the other computing bridge — a graph becomes a matrix, and then linear algebra answers questions about it. Compare markov-chain, where a finite chain is a transition matrix; the move is the same one and this spoke now records it twice.

What one course does not cover

grinberg-graph-theory is a quarter, deliberately weighted toward "the discrete and algebraic sides," and the shape of what it leaves out is as informative as what it holds. Planarity and the four-colour theorem are gone because they need continuity — no analysis is a prerequisite of the text and planar embedding cannot be had without one. Infinite graphs, random graphs, extremal graph theory beyond Turán, spectral methods and algorithms are absent for the ordinary reason that a quarter is ten weeks.

He also names about twenty-five other textbooks and observes that past the basics they cover different ground from each other.

The second route (2026-08-30)

harju-graph-theory is that map's other half, and the fit is almost suspiciously good: 98 pages of lecture notes from the University of Turku whose Chapter 5, Graphs on Surfaces, is exactly the chapter Grinberg declines to write.

Now covered, and previously not:

Planar graphs — plane embeddings, faces, Euler's formula, and Kuratowski's theorem characterising planarity by forbidden subdivisions of K₅ and K₃,₃.
Colouring planar graphs — the five-colour theorem proved, the four-colour theorem stated, and map colouring set up through the dual graph.
Genus — embeddings on surfaces above the plane, and Euler's formula generalised to ν − ε + φ = 2 − 2g (proof omitted, Mohar & Thomassen cited).
Ramsey theory — a section of its own inside the colouring chapter, absent from the other text.
Network flows — max-flow-min-cut developed in the digraph chapter. Grinberg reaches flows too, and uses them to derive Hall; here they arrive last, as the application.

How the topology gets paid for. Grinberg's argument was that planarity cannot be done without analysis or topology, so it goes. Harju agrees about the requirement and answers it differently, in a sentence at the top of the chapter: "The geometry of the plane will be treated intuitively." He then builds region and continuous curve by hand out of open sets and proceeds. The subject does not have two theories of planarity; it has two ways of handling a prerequisite the reader lacks — drop the material, or keep it and say plainly where the rigour was lowered.

Still missing after two texts: infinite graphs, random graphs, extremal theory beyond Turán, spectral graph theory, and algorithms as a subject. Both books name the complexity boundary (NP-completeness appears in Harju's opening notation section) and neither implements anything. The algebraic side — Biggs, Godsil & Royle — is handed off by both.

Connections

grinberg-graph-theory — the first source: a graduate quarter, algebraic side, no planarity
harju-graph-theory — the second: lecture notes carrying planarity, genus, Ramsey and flows
matrix-tree-theorem — spanning trees counted by a determinant
linear-algebra — adjacency and Laplacian matrices; determinants are the text's real prerequisite
markov-chain — the other place in this spoke where a finite structure is handled as a matrix
abstract-algebra — polynomial and matrix rings, and 𝔽₂, appear in a few proofs
gallier-quaintance-math-deep — graph Laplacians and spectral graph drawing, reached from linear algebra (Part I, ch. 20–21) rather than from combinatorics; the third source on the subject and the only one that treats a graph as a matrix from the start
mathematics — the root page