Harju — Lecture Notes on Graph Theory
Tero Harju's course notes from the Department of Mathematics at the
University of Turku, 98 pages, with "1994 – 2012" on the title page. The
PDF held in raw/ was produced on 2014-04-24 by dvips and Ghostscript from LaTeX, which is the
only date the file itself carries — no published: is recorded here, because an eighteen-year span
and a typesetting timestamp are not a publication date.
It arrived as the corpus's second graph theory text, and it covers most of what the first one deliberately left out.
Contents
| Ch. | Subject | Pages |
|---|---|---|
| 1 | Introduction — graphs and plane figures, subgraphs, paths and cycles | 2–15 |
| 2 | Connectivity — bipartite graphs and trees, connectivity | 16–28 |
| 3 | Tours and matchings — Eulerian, Hamiltonian, matchings | 29–41 |
| 4 | Colourings — edge colourings, Ramsey theory, vertex colourings | 42–59 |
| 5 | Graphs on surfaces — planar graphs, colouring planar graphs, genus | 60–81 |
| 6 | Directed graphs — digraphs, network flows | 82–94 |
Dense for its length: roughly 215 numbered theorems, 88 lemmas, 65 definitions and 54 worked examples in 98 pages, with starred sections marked optional. Harju names Bondy & Murty, Diestel, Harary, West and Wilson as the books the material follows, and says outright that these lectures treat combinatorial aspects, pointing at Biggs and at Godsil & Royle for the algebraic side and Even for algorithms.
The chapter that answers Grinberg
grinberg-graph-theory drops planarity and the four-colour theorem on principle: no analysis is a prerequisite of that text, and a proof that K₅ has no crossing-free drawing "must use some analysis or topology." graph-theory and synthesis both record that as a syllabus cut by a prerequisite list.
Harju keeps the chapter and pays the bill in a different currency. He states the terms in one sentence:
The geometry of the plane will be treated intuitively.
Then he defines a region and a continuous curve by hand from open sets of ℝ×ℝ, proves Euler's formula, gives Kuratowski's characterization, treats the four-colour theorem and its five-colour predecessor, and extends to embeddings on surfaces of higher genus — omitting the proof of the genus form of Euler's formula and pointing at Mohar & Thomassen for the rest.
So the two texts do not disagree about the mathematics; they disagree about what to do with the debt. Both accept that a rigorous treatment of planarity needs topology the reader does not have. Grinberg refuses the debt and loses the chapter. Harju takes the chapter and pays with a stated reduction in rigour, confined to one place and announced in advance. Neither is hiding anything, which is what makes the pair usable as evidence rather than as opinion.
Exercises: there are none
The pedagogical contrast with the first text is sharp. Grinberg prints 116 numbered exercises and no solutions. Harju prints no exercise sets at all. The word "exercise" appears ten times in 98 pages, always inline and always as a handoff — "Proof. Exercise." under a stated theorem, or "we leave the following statement as an exercise" mid-paragraph. A handful of proofs are simply omitted with a citation instead (Cayley's formula for the number of labelled trees, the existence of stable matchings, the genus form of Euler's formula).
For a spoke that reads exercise design as a pedagogical decision, this is the minimal case: the reader's work is not organised into a problem set, it is scattered through the proofs as gaps the lecturer expects to be filled in the room.
Two more things the text does
It teaches its own open problems. Harju says he mentions "several open problems that have gained respect among the researchers," and does — the point being that graph theory can state hard unsolved questions early, which is not true of most subjects in this corpus.
It keeps computational complexity in view without doing algorithms. NP-completeness is introduced in the notation section of the introduction, and the text returns to it: Hamiltonian-type questions are flagged as hard where Eulerian ones are cheap, and the planarity chapter notes that linear-time planarity testing exists while being "rather difficult to implement," citing Auslander & Parter (1961) via Skiena. Same posture as grinberg-graph-theory — name the complexity boundary, decline to implement anything.
No licence, and no statement of one
Searched in full: the text contains no copyright notice and no licence of any kind. It is a PDF on a university web server, freely downloadable, with nothing said about what may be done with it.
That is a third position on this spoke's access axis, and it is not the same as either existing one. Commercial texts state terms and charge (larsen-marx-mathematical-statistics, lal-algebra-1); the free ones state terms and don't (grinberg-graph-theory CC0, hefferon-linear-algebra, trench-real-analysis). This one is free to obtain and legally silent — the common condition of lecture notes on personal university pages, and the first instance the corpus holds. See Paid first, free second in synthesis.
Connections
graph-theory — the subject page, which had one route through it and now has two · grinberg-graph-theory — the first text, and the one this answers · tero-harju · university-of-turku · mathematics · synthesis