Quick Answer: Graph theory for beginners starts with three ideas: vertices, edges, and degrees. Mikhail Lavrov's free textbook, Start Doing Graph Theory, teaches these by solving puzzles and proving theorems instead of memorizing definitions. It's licensed under CC BY-SA 4.0, so you can read it online or download the PDF at no cost.
Most people meet graph theory as a list of definitions they never use. You learn what a vertex is, what an edge is, and then nothing happens. The fastest way in is different: pick a puzzle, draw a picture, and ask what structure makes the puzzle solvable. Lavrov's Start Doing Graph Theory is built around that approach, and it's one of the better entry points I've seen for a field that rewards doing over reading. It surfaced on Hacker News, which is how many readers first found it.
Why Start with Puzzles Instead of Definitions
Definitions in graph theory are short. The hard part is knowing when a definition applies. A graph is just a set of vertices joined by edges, but almost every useful question asks about what that structure forces. Can you walk every edge exactly once? Can you color the vertices so no two neighbors match? Can you pair up tasks and workers without a conflict?
Puzzles give you a reason to care about the definitions. Here's the practical benefit: when you're stuck on a puzzle, you're forced to reformulate it as a graph question, and that reformulation is the actual skill. Most learners who skip this step can recite the vocabulary and still can't model a new problem.
The book's premise is that you learn the field by using it. That's a sound bet for a textbook, though it means you'll spend more time with pencil and paper than with reference tables.
The Three Ideas You Need First
Before any theorem, you need three working concepts:
- Vertices are the objects you're modeling: people, cities, states, moves in a game.
- Edges record a relationship between two vertices: friendship, a road, a legal move.
- Degree is the number of edges touching a vertex.
Degree looks trivial, and it isn't. The handshake lemma says that the sum of all vertex degrees equals twice the number of edges, because every edge is counted at both of its endpoints. That fact alone rules out many impossible configurations. If you're told a party had seven people and each shook hands with exactly three others, you can conclude it's impossible before drawing anything: 7 × 3 = 21 is odd, but the sum of degrees must be even.
This is the kind of result the book trains you to find. Spot the invariant, and a whole class of "can this exist?" questions collapses quickly.
Euler's Bridges and Where the Field Started
Most histories of graph theory begin in 1736, when Leonhard Euler analyzed the seven bridges of Königsberg. The question was whether a walk could cross each bridge exactly once and return to the start. Euler's key move was to ignore the geography. He reduced each land mass to a vertex and each bridge to an edge, then asked a purely structural question.
His answer depended on degrees. A walk that starts and ends at the same place, using every edge once, is an Euler circuit. It exists only if every vertex has even degree. A walk that starts and ends at different vertices is an Euler path, and it requires exactly zero or two vertices of odd degree. Königsberg had four land masses, each with an odd number of bridges, so neither was possible.
Here's where most beginners get tripped up. They assume the problem is about distance or layout. It isn't. Move the bridges around on a map, keep the connections the same, and the answer stays the same. That's the counter-intuitive point: graph theory deliberately throws away geometry, which is exactly why it applies to so many unrelated domains.
That said, this only settles existence. Euler's criterion tells you whether a circuit exists, not how to find one efficiently. Fleury's algorithm and Hierholzer's algorithm both construct Euler circuits, and you should know which one fits your problem before you implement either.
Proofs Are the Real Skill
The popular advice is to learn the algorithms first and the theory later. That's incomplete. Algorithms tell you how to compute an answer for one instance. Proofs tell you what must be true for every instance, and that's what lets you handle a problem you've never seen.
Take Ramsey-style reasoning. Among any six people, either three of them all know each other or three of them are all strangers to each other. That's the statement R(3,3) = 6, and the proof is a short counting argument on the edges of a complete graph. You don't need to memorize the number to benefit from the method. You need to see why six is enough and five isn't.
This is where Lavrov's book earns its keep. It treats proof as the central activity, so you practice the move that matters most in research: take a claim, look for the structure that forces it, and write down why. Expect this part to be slower than you'd like. It's also the part that transfers.
Here's the trade-off to be honest about. If your goal is to write software that finds shortest paths in a logistics network next month, you can get there faster with an applied course. If your goal is to reason about combinatorial structures, the proof-based route pays off more.
Where Graph Theory Shows Up in Practice
Graph theory runs through networking, scheduling, compilers, chemistry, social network analysis, and more. In most real systems, the hard part isn't the algorithm. It's getting the model right.
A common failure mode: treating a directed relationship as undirected. If you model a dependency graph for a build system as undirected, you lose the information about which task must finish first, and your topological sort produces nonsense. Another: confusing a graph with a multigraph when two entities can share more than one relationship. Both mistakes come from a loose translation of the real problem into graph language, and both are easy to make when you've only memorized definitions.
For hands-on work, the NetworkX graph library for Python is the standard starting point. It lets you build small graphs, compute degrees, and test an Euler criterion in a few lines. Pair it with Graphviz for drawing, and you can check your pencil-and-paper reasoning against code. Use the code to verify, not to replace the proof.
Graph coloring has a famous milestone too. The Four Color Theorem proof by Kenneth Appel and Wolfgang Haken, completed in 1976, showed that any planar map can be colored with four colors so that no neighboring regions share a color. The proof relied on a computer checking a large set of cases, and some mathematicians found that uncomfortable at the time. The nuance matters: the result is accepted, but whether a computer-assisted proof offers the same kind of insight is still debated. That's a useful question to carry into any proof-heavy text.
How to Work Through the Book Without Getting Stuck
Pick a format based on how you learn, then commit to a routine. Here's a comparison:
| Format | Best for | Main trade-off |
|---|---|---|
| Read online (vertex.degree) | Quick chapter lookups, browsing the table of contents | Harder to annotate and take notes |
| Download the PDF | Offline reading, marking up with a tablet or printing | Doesn't update automatically if the text changes |
| Paper notebook alongside | Working puzzles and proofs by hand | Slower to check your work |
| NetworkX in Python | Testing conjectures on small random graphs | Can make you rely on code instead of reasoning |
A routine that works:
- Read one section and stop at the first puzzle.
- Draw a small graph and try three examples by hand.
- Write down the invariant you noticed, such as a degree count or a parity argument.
- Attempt the proof before checking the solution.
- Model one real problem from your own work as a graph, even a messy one.
Step 4 is where most people quit. Sit with the failed attempt for ten minutes before reading the answer. The struggle is where the learning happens.
Frequently Asked Questions
What is graph theory used for?
Graph theory models any system made of objects and pairwise relationships. It's used in network routing, scheduling, compiler design, chemistry (molecular structures), and social network analysis. Its strength is that it discards irrelevant detail and keeps only the connection structure, which is often all you need to answer whether a configuration is possible.
How to use graph theory to solve puzzles?
Start by identifying the objects as vertices and the allowed moves or conflicts as edges. Then ask what structural property the puzzle depends on, such as parity of degrees, connectivity, or coloring constraints. Test small cases by hand, look for an invariant, and try to prove why it holds. The model is usually more important than the algorithm.
Is Start Doing Graph Theory free to read?
Yes. Mikhail Lavrov's textbook is licensed under CC BY-SA 4.0, which lets you read it online or download a PDF at no cost. The license also allows you to share and adapt the material, provided you credit the author and license any derivative work the same way.
Do I need a math background to start?
Basic comfort with sets, functions, and logical reasoning helps. You don't need calculus. Most of the early material is combinatorial, so careful counting and patience with proofs matter more than advanced prerequisites. If a proof stalls you, reread the definitions and draw a smaller example before moving on.
When should I use graph theory instead of a spreadsheet?
Use graph theory when relationships between items matter more than their individual attributes. If you're tracking sales by region, a spreadsheet works. If you're asking which tasks can run in parallel, which dependencies create cycles, or whether a schedule has conflicts, a graph model usually makes the question easier to state and answer.
Try this week: pick one scheduling or dependency problem from your own work, draw it as a graph with five or fewer vertices, and check whether any vertex has odd degree. Note what the answer tells you before you write any code. Pass this to a colleague who keeps trying to solve routing problems with nested loops and a prayer, and point them to Start Doing Graph Theory as the place to begin with graph theory for beginners.