Grinberg — An introduction to graph theory
darij-grinberg's course text for Math 530 at drexel-university, Spring 2022, posted to
arxiv as 2308.04512 in August 2023 and revised twice since; the copy held in raw/ is the
Spring 2025 edition of 7 June 2025 (v3), 454 pages. An earlier and similarly structured version
was taught at the University of Minnesota in Spring 2017, whose course page still carries solutions
to some exercises.
Re-sent by the curator 2026-09-17 and the arXiv listing re-read: still v3, which arXiv stamps
8 June 2025 (UTC) against the edition date of 7 June printed in the PDF — the same version, one day
apart across a timezone. Nothing to refresh; the page stands as read from the held PDF.
Released under CC0 1.0 Universal — a public-domain dedication, which asks for nothing back, not even attribution. That makes it the most permissive licence in this corpus, ahead of mari-measurement-across-sciences (CC BY 4.0) and well ahead of the NC-restricted texts (keisler-elementary-calculus, trench-real-analysis, illowsky-introductory-statistics).
It opens graph-theory here, and closes the graph half of growth edge 10 — discrete mathematics and combinatorics. Counting and recurrences are still unheld; see the honest accounting below.
What it is
A quarter-long graduate course (the author allows advanced undergraduates), 116 numbered exercises without solutions, 88 numbered theorems on top of the propositions, lemmas and corollaries. Ten chapters:
| Ch. | Subject | Pages |
|---|---|---|
| 2 | Simple graphs — degrees, isomorphism, walks and paths, cycles, bridges, dominating sets, Hamiltonian paths (Ore, Dirac) | 9–76 |
| 3 | Multigraphs — conversions from simple graphs, Eulerian circuits, Euler–Hierholzer | 77–104 |
| 4 | Digraphs and multidigraphs — in/outdegrees, strong vs weak connectedness, the adjacency matrix, tournaments and the Rédei theorems | 105–151 |
| 5 | Trees and arborescences — leaves, spanning trees and forests, centers, arborescences, the BEST theorem, the matrix-tree-theorem, de Bruijn sequences, Laplacians | 152–291 |
| 6 | Colorings — 2-colorings, Brooks, the chromatic polynomial, Vizing, and a section on results proved since 2019 | 292–319 |
| 7 | Independent sets — Caro–Wei, Turán, digraph kernels | 320–336 |
| 8 | Matchings — bipartite graphs, Hall's marriage theorem, König, Latin squares, Birkhoff–von Neumann | 337–367 |
| 9 | Networks and flows — max-flow-min-cut, then Hall–König derived from it | 368–391 |
| 10 | More about paths — the four Menger theorems, Gallai–Milgram, Elser's sums | 392–441 |
Chapter 5 is a third of the book (140 pages), and the Matrix-Tree complex alone runs 65 of them — statement, proof, the undirected version, de Bruijn sequences, Laplacian nullspaces and a weighted generalisation. If this text has a centre, that is it.
The prerequisite that decides the syllabus
Grinberg lists what a reader needs: "the basic properties of determinants, polynomials and finite sums," with rings and fields mentioned occasionally (ℚ, ℝ, polynomial and matrix rings, and 𝔽₂ in a few places). Then the line that matters:
No analysis (or even calculus) is required anywhere in this text.
Every other subject in this spoke descends from calculus or from probability. This one does not touch either. A graduate text sitting entirely outside the corpus's spine is new here, and it comes with the determinant as its one heavy import — which is exactly what Chapter 5 spends itself on (linear-algebra arriving as graph theory's working tool, the way it arrives as probability's in markov-chain).
The prerequisite is not free, and the book shows the bill. Planarity and the four-colour theorem are absent — mentioned twice, both times handed off to another textbook. The reason is given the first time, when he asks whether K₅ can be drawn without crossings:
Note that any proof must use some analysis or topology, since the result relies on the notion of a (continuous) curve in the plane.
So the most famous corner of introductory graph theory is out because the prerequisite list rules it out. That is a syllabus decision made by a prerequisite decision, stated in the open, and this corpus has not seen one before — carroll-geometric-function-theory's §1.4 lists omissions but justifies them by taste and length, not by what the reader was told they would need.
Twenty-five other books, and no agreement among them
The preface names roughly twenty-five competing texts, split into "comprehensive works" and "more introductory" ones, and then says of them:
These texts are written at different levels of sophistication, rigor and detail, are tailored to different audiences, and (beyond the absolute basics) often cover different ground.
His own notes "are self-contained and do not follow any existing book," and their focus is "the more discrete and algebraic sides of graph theory (finite graphs of various kinds, existential results, counting formulas)" — limited, he says, by the quarter and by "the limits of my own knowledge."
carroll-geometric-function-theory found that consensus in complex analysis evaporates at the second course. Graph theory has no such consensus at the first one, and the subject's short history is the likeliest reason: Euler's 1736 Königsberg paper, some scattered 19th-century work, and then, in Grinberg's word, it "straight-up exploded" in the 20th.
What the book does with algorithms
Two subsections called "Remark on algorithms" (§2.9.4 for graphs, §4.5.3 for digraphs), and the stance is stated at the top of the first: "we will only scratch the surface and content ourselves with simple but not quite optimal algorithms."
They are still the sharpest pages in the book for a computing reader. Five questions are posed about
walks and paths from u to v; four of them collapse into one recursive procedure that runs in
polynomial time. The fifth — find a path of exactly length k — is separated deliberately:
Question 5 looks superficially similar to Question 4, yet it differs in the most important way: There is no efficient algorithm known for answering it!
He names it NP-hard, notes the trivial n^(k+1) check for fixed k, and observes that ruling out a
polynomial algorithm "appears near-impossible to prove at the current stage of the discipline." The
weighted version of Question 3 is the shortest-path problem, and he forwards it to five
algorithm-focused texts rather than treating it.
A textbook with an open problem in it
§6.8, "Some recent results," is a page of live research inside an introductory course. A 1971 conjecture of Tomescu on the number of proper k-colorings was proved only in 2019, by Fox, He and Manners; a more general form of it is still unsolved. Grinberg cites the paper, and then cites a MathOverflow answer for a clearer version of one proof.
Citing MathOverflow in a course text is a small thing, but no other source in this spoke does it. The texts here send the reader to books.
Pedagogy, offered as opinion
The exercises get a paragraph that is this corpus's recurring move — a teaching claim made in a preface, with nothing behind it:
Naturally, one person's inspiration is another's distraction, so I do not recommend assigning too much importance to any specific exercise; it is usually better to read on than to dwell for hours. However, a dozen minutes of thought per exercise will likely not be a waste of time.
Almost all exercises are optional, in the strict sense that the text never uses them. Compare corral-vector-calculus, whose 420 graded exercises carry the course, and carroll-geometric-function-theory, which prints 54 pages of full solutions. Three books, three incompatible theories of what an exercise is for, none of them tested.
The first result in the book, at page 14, is that R(3,3) = 6: any graph on six vertices contains three mutually adjacent or three mutually non-adjacent vertices. Reaching a real Ramsey-theoretic theorem five pages after the definition of a graph is a deliberate choice about how long a reader should be made to wait.
Tier and what it can support
T1 — the author's own text, primary, posted under his name with an institutional address and an errata channel, and revised across three versions over two years. The usual textbook caveat applies (mathematics → the level a text is pitched at is part of its evidence): this is one mathematician's quarter, self-described as bounded by his own knowledge, and it should not be read as a survey of what graph theory is.
What it establishes: the definitions, the standard first-course results with proofs, and the algebraic route through spanning trees. What it cannot: planarity, extremal and random graphs, spectral graph theory beyond Laplacian counting, algorithms as a subject, or anything about infinite graphs — which he closes off in a parenthesis, "I shall leave this can of worms closed for this quarter."
Growth edge 10, half closed
The edge asked for an open-licensed discrete-mathematics and combinatorics text and named three things: counting, recurrences, graphs. This closes graphs, over-closes it for a first course, and leaves the other two exactly where they were. Enumerative combinatorics is repeatedly pointed at here — Grinberg refers the reader to Stanley and to Galvin for the combinatorial proofs he does not give — so the residue can be named precisely instead of the edge being ticked off.
Connections
- graph-theory — the subject this opens
- matrix-tree-theorem — the book's deepest single development
- linear-algebra — determinants as the one prerequisite that does real work here
- darij-grinberg · drexel-university · arxiv
- carroll-geometric-function-theory — the other text here that argues about what a syllabus is
- judson-abstract-algebra — the other free-licensed text whose author kept maintaining it