Start Doing Graph Theory

Start Doing Graph Theory

TL;DR: Start Doing Graph Theory is a free, proof-based introduction to graph theory by mathematician Mikhail Lavrov, expanded from lecture notes he taught at Kennesaw State University and released under a Creative Commons licence. It hit the front page of Hacker News in late October 2026 with over 560 points, mostly because working engineers recognised their own job in it. This guide covers what is actually inside the book, why graph theory pays off in real projects, and how to start this week with runnable Python rather than notation you will forget.

Most people meet graph theory twice in their life: once in a discrete maths course they barely remember, and once in a job interview where someone asks them to detect a cycle in a dependency list. Between those two moments, graph theory quietly runs a large share of the software you use every day โ€” routing engines, package managers, schedulers, social feeds, fraud detection.

Which is why a free textbook with an unusually blunt title got 560-plus points on Hacker News on 29 October 2026. The title is an instruction, not a brand: start doing graph theory, today, on paper and in a REPL.

The book is Start Doing Graph Theory by Mikhail Lavrov, published in full on his site vertex.degree as HTML and as a downloadable PDF, under a CC BY-SA 4.0 licence. The author states plainly that it is free to download and read, and will remain so.

The submission โ€” posted by user ibobev โ€” reached the front page within hours, and the comment thread is more interesting than the vote count. The most-upvoted replies came from people who use graphs professionally, and what they described was not academia. It read like a job description:

  • A routing engineer explaining that a street network is “a directed graph, all the way down”, with A* for point-to-point queries, bidirectional A* to cut search time, Dijkstra flood-fills to establish a cost budget for turning back, and Tarjan’s algorithm to make sure the search never ends up trapped in a disconnected island.
  • Someone using Menger’s theorem โ€” formally, a statement about how many vertex-disjoint paths exist between two points โ€” as a practical test for whether a loop back to the origin is even buildable.
  • Several practitioners admitting they use far less of the theory than they know, and that this gap is normal: most days you need BFS, a topological sort, and the ability to reason about connectivity, not Tutte’s theorem.

There was also a very 2026 tangent: a subthread worrying about whether a new maths book could have been machine-written, with others pushing back that the suspicion now lands on every author by default. The practical answer was the right one โ€” a proof is either checkable or it is not, and this book asks you to check.

What is actually inside this graph theory book

Start Doing Graph Theory is not a survey or a formula sheet. The graph theory it teaches is seven parts plus an appendix, built around problems first and definitions second, and it is explicitly proof-based: two of its chapters are about how to write proofs at all, and each proof in the book pauses to explain why anyone would think to try that move.

Here is the map, in the order the book teaches it.

Part Core material What it unlocks in practice
1. The Beginning Modelling puzzles as graphs (colouring Switzerland’s cantons, the seven dwarfs, Towers of Hanoi, a tiling puzzle, placing cameras efficiently, matching cars to drivers); isomorphism and graph invariants; walks, paths, cycles; vertex degree and the handshake lemma Turning a messy real problem into V and E โ€” the step almost everyone skips
2. Vertex Degrees Degree sequences, regular graphs, the Petersen graph, the degree/diameter problem, Havelโ€“Hakimi, multigraphs and digraphs, Euler tours Deciding whether a spec is even possible before you build it
3. Trees Spanning trees, bridges, induction on trees, Cayley’s formula and Prรผfer codes, directed acyclic graphs, topological orders, condensation Build systems, dependency resolvers, org charts, decision logic
4. Matchings Bipartite graphs, Kรถnig’s theorem, Hall’s theorem, augmenting paths, Tutte sets, 1-factorisations Assignment problems: riders to orders, jobs to machines, students to classes
5. Hard Problems Hamilton cycles and knight’s tours, cliques and independent sets, Ramsey numbers, greedy colouring, Sudoku as graph colouring, line graphs, De Bruijn sequences, Vizing’s theorem Recognising NP-hardness early enough to stop optimising and start approximating
6. Planar Graphs The three-utilities puzzle, Euler’s formula, faces, triangulations, graph minors, the Platonic and Archimedean solids, dual graphs, the four colour theorem Circuit and PCB layout, map rendering, network topology limits
7. Connectivity Cut vertices, 2-connected graphs, ear decompositions, Menger’s theorem, network cuts, maximum flow, the Fordโ€“Fulkerson algorithm Reliability engineering, capacity planning, bottleneck analysis
Appendix Review of proof-writing The prerequisite you were never formally taught

Two things stand out about the design. First, the book is unapologetic about multigraphs and digraphs being exceptions rather than the default โ€” Lavrov argues that keeping loops and parallel edges out of the first six chapters removes complexity you do not need yet, which is rare in a graph theory text. Second, the practice problems are everywhere, and they are the point: the preface asks you to stop and think before reading each answer, which is the behaviour a PDF of formulas cannot force.

Lavrov is not a hobbyist: a PhD from Carnegie Mellon’s Algorithms, Combinatorics and Optimization programme in 2017, teaching at the University of Illinois Urbana-Champaign, then Kennesaw State, plus every summer at Canada/USA Mathcamp since 2014. The book grew out of his own graph theory course, reorganised and expanded around what students actually got stuck on.

How to start doing graph theory in Python this week

The fastest way to make graph theory stick is to alternate: read a section, then implement the idea in twenty lines. You do not need a graph library to begin. An adjacency dictionary is a graph, and the first four graph theory chapters map almost one-to-one onto code you can write in an afternoon.

1. A graph is a dictionary, and BFS is level order

Take a stretch of KL’s MRT Kajang line as an adjacency dict where a station’s neighbours are the stations one stop away. Finding the fewest hops between two stations is then breadth-first search, and behaviour like “0 hops from a station to itself” falls out of the code for free.

from collections import deque

kajang_line = [
    "Bukit Bintang", "Tun Razak Exchange", "Cochrane", "Maluri",
    "Chan Sow Lin", "Pudu", "Plaza Rakyat", "Masjid Jamek",
    "Bandaraya", "Bank Negara",
]
rail = {s: set() for s in kajang_line}
for a, b in zip(kajang_line, kajang_line[1:]):
    rail[a].add(b)
    rail[b].add(a)

def hops(graph, start, goal):
    queue = deque([(start, 0)])
    seen = {start}
    while queue:
        node, d = queue.popleft()
        if node == goal:
            return d
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, d + 1))
    return None

print("hops Bukit Bintang -> Masjid Jamek:", hops(rail, "Bukit Bintang", "Masjid Jamek"))
print("hops Bank Negara -> Pudu:", hops(rail, "Bank Negara", "Pudu"))

Running it prints 7 and 4. Two details in that snippet are pure graph theory rather than Python: the seen set is what stops a cycle from looping forever, and len(rail[station]) is the station’s degree. The handshake lemma in Part 1 โ€” that degrees sum to twice the number of edges โ€” is the kind of statement you can verify against your own data in one line, which makes it a useful sanity check on any edge list someone hands you.

2. The handshake lemma’s cousin: is this degree sequence even buildable?

Someone asks for a system where seven services have to talk to 5, 5, 4, 3, 3, 2 and 2 others respectively. Before writing any code, ask whether such a graph exists at all. Havelโ€“Hakimi answers it by repeatedly taking the greediest vertex, connecting it to the greediest others, and checking you never go negative.

def is_graphic(seq):
    seq = sorted(seq, reverse=True)
    while seq:
        d = seq.pop(0)
        if d < 0 or d > len(seq):
            return False
        for i in range(d):
            seq[i] -= 1
        if any(x < 0 for x in seq[:d]):
            return False
        seq.sort(reverse=True)
    return True

for s in ([3, 3, 2, 2, 2, 2], [4, 4, 3, 3, 2, 2], [5, 4, 3, 2, 1, 0]):
    print(s, "-> graphic:", is_graphic(list(s)))

Verified output: the first two sequences are graphic, [5, 4, 3, 2, 1, 0] is not โ€” a vertex claiming degree 5 needs five partners, and after wiring them up the leftovers cannot satisfy each other. This is the cheapest possible form of requirement review, and it comes straight out of Part 2.

3. DAGs and topological order, which is most of your build pipeline

Part 3’s chapter on directed acyclic graphs is the one that pays rent immediately. Model a data pipeline as dependencies, run Kahn’s algorithm, and you get a legal execution order; add a cycle and you get a None instead of a hung CI job.

deps = {
    "config":     [],
    "schema.sql": ["config"],
    "etl_job":    ["schema.sql"],
    "dbt_models": ["etl_job"],
    "api":        ["schema.sql", "config"],
    "smoke_test": ["api", "dbt_models"],
    "release":    ["smoke_test"],
}

def topo_order(deps):
    indeg = {n: len(ds) for n, ds in deps.items()}
    ready = [n for n, k in indeg.items() if k == 0]
    order = []
    while ready:
        n = ready.pop()
        order.append(n)
        for m, ds in deps.items():
            if n in ds:
                indeg[m] -= 1
                if indeg[m] == 0:
                    ready.append(m)
    return order if len(order) == len(deps) else None

print(topo_order(deps))
print(topo_order({"a": ["c"], "b": ["a"], "c": ["b"]}))

The first call returns a valid order โ€” config, schema.sql, api, etl_job, dbt_models, smoke_test, release โ€” and the second returns None, because a three-node cycle means no vertex ever reaches in-degree zero. That len(order) == len(deps) check is the cycle detector underneath npm, pip and every scheduler you have debugged.

4. Euler tours, or “can this route be walked once?”

Part 2’s Euler tour chapter turns the puzzle of drawing a shape without lifting your pencil into a two-line test: count the vertices of odd degree. Zero odd vertices means a closed tour exists; exactly two means an open trail is possible; anything else means no.

def has_euler_tour(graph):
    odd = [v for v in graph if len(graph[v]) % 2]
    return {
        "odd_degree_vertices": sorted(odd),
        "euler_circuit": len(odd) == 0,
        "euler_path": len(odd) in (0, 2),
    }

square = {"a": {"b", "d"}, "b": {"a", "c"}, "c": {"b", "d"}, "d": {"a", "c"}}
with_diag = {"a": {"b", "c", "d"}, "b": {"a", "c"}, "c": {"b", "a", "d"}, "d": {"a", "c"}}

print(has_euler_tour(square))
print(has_euler_tour(with_diag))

The bare square has zero odd vertices, so it admits a closed tour. Add one diagonal and exactly two vertices go odd, so you can still draw it in one stroke but not finish where you started. This is the exact reasoning behind snow-plough routing, mail delivery runs and warehouse pick paths.

Why graph theory earns its keep on a Malaysian dev salary

Graph theory shows up in job descriptions here without ever using the word. A short, honest list of where it is load-bearing:

  • Delivery and ride-hailing routing. A road network is a weighted digraph; A* and Dijkstra are the reason a quote arrives in 200 ms. Batching orders to riders is bipartite matching โ€” Part 4, almost literally.
  • Package and build tooling. Dependency resolution is a DAG with a topological order, and “peer dependency conflict” is a cycle or a constraint the graph cannot satisfy.
  • Manufacturing and MES work. Shop-floor process flows, machine-to-job assignment, and fixture scheduling are assignment and flow problems. If you have ever balanced welders across stations by hand, you were approximating a matching.
  • Fraud and abuse detection. Shared devices, shared bank accounts, shared addresses form a graph; rings show up as dense clusters and short cycles.
  • Interviews. Topological sort, unionโ€“find, shortest path and grid BFS are standard at KL engineering shops, and they are also the four things this graph theory book makes you able to derive instead of memorise.

There is a second, more local reason to care. Malaysian CS degrees do teach discrete maths โ€” graph theory appears in the syllabus at UM, UTM, USM, MMU and APU among others โ€” but the part that gets compressed in a 14-week semester is exactly the part that makes it useful: modelling a problem you have never seen before. A free book with a practice problem on every other page patches that gap, and the PDF works offline on a phone.

Proofs: the graph theory skill self-taught developers skip

Most developer-facing “learn graphs” material stops at algorithms, which is why so many engineers can implement Dijkstra and still be unable to argue that their solution is correct when the test suite did not cover a constraint.

Start Doing Graph Theory is a proof-based introduction, and it says so. Two chapters โ€” one early, one in the appendix โ€” are about proof-writing itself, on the assumption that many readers arrive without ever having written one. Every proof in the text pauses to explain the reasoning behind its first move, which is the difference between reading a magic trick and learning one.

The handshake lemma is the cleanest illustration. The claim is that the degrees of all vertices sum to twice the number of edges, and the proof is one sentence: every edge contributes exactly two to the total, once at each end. That is not a trick you will forget, and it is the reason a quick sum(degrees) % 2 == 0 assertion can catch a corrupt edge list in production. Proof, in graph theory, is not ceremony โ€” it is the justification for the check you are about to ship.

Expect to be slower than you want: the book asks questions before answering them.

A six-week plan to start doing graph theory

Forty-five minutes a day, paper for proofs and an editor for algorithms. The graph theory book is long, so pick a spine instead of reading linearly.

  • Week 1. Part 1, plus the appendix chapter on proof-writing. Do the practice problems with a pen. Goal: given a word problem, write down V and E.
  • Week 2. Finish Part 1 (walks, cycles, degrees). Implement BFS and re-derive the handshake lemma from your own edge lists.
  • Week 3. Part 2. Implement Havelโ€“Hakimi and the Euler tour test. Note how often the answer is “impossible”, not “hard”.
  • Week 4. Part 3. Implement topological sort and use it on a real dependency file from your own repo.
  • Week 5. Part 4. Model one assignment problem you actually have โ€” riders to orders, jobs to machines, reviewers to papers โ€” and solve it with augmenting paths.
  • Week 6. Skim Parts 5 and 6 for vocabulary (NP-hardness, planarity, colouring), then pick one small project and finish it. A visualiser for one algorithm beats five unfinished chapters.

Skip Part 7 until you need it; connectivity and max flow are excellent material and also the easiest place to stall.

FAQ

Is the book really free, and will it stay free?
Yes. Both the text and the site are licensed CC BY-SA 4.0, and the author states that the HTML and PDF will remain free to download and read. You can read it in the browser or keep the PDF offline.

Do I need calculus or linear algebra before starting graph theory?
No. The real prerequisite is comfort with sets and induction, and the book includes proof-writing chapters precisely because many readers arrive without that. If induction is shaky, work the appendix first.

Is this enough graph theory for coding interviews?
It is enough for the ideas. Graph theory gives you the vocabulary and the correctness argument โ€” cycles, topological order, bipartiteness, matching, shortest paths โ€” and it tells you why each applies to the problem in front of you. It is not a speed drill. Use it to understand why an approach works, then practise implementation separately.

Can I use it for a class, a study group, or a translated copy?
CC BY-SA 4.0 permits redistribution and adaptation, including commercial classroom use, provided you credit the author and release derivatives under the same licence.

Does graph theory still matter now that LLMs write code?
More, not less. Routing, scheduling, capacity planning and dependency resolution are deterministic problems with checkable answers, so the durable skill is recognising the graph structure and knowing which theorem applies. Models are good at producing an implementation once the problem is framed; framing it is still your job.

Start with one graph theory problem, not one chapter

The book’s argument is in its title: you cannot learn mathematics by reading it, any more than you can learn to swim by watching. So the productive move is not “read a graph theory textbook” โ€” it is to open Chapter 1, pick the puzzle you find least obvious (colouring Switzerland’s cantons is a good one), and spend twenty minutes failing at it before reading the answer.

From there, alternate: one section, one implementation. Each snippet above โ€” the stations search, the degree-sequence check, the build-order sort โ€” is a chapter compressed into twenty lines, and something you can point at in a code review next week.

The book is free, the PDF is offline-friendly, and the first chapter is one click away. That is about as low as the barrier to start doing graph theory gets.

More from ZFRBuild

Related Article