Free public beta until December 4, 2026:
every course is open, no card needed.
After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept.
How the beta works
Chapter 0 wrap-up
Readiness: the graph-theory toolkit
Closing thought
Every idea on this page is a question about one object: dots and the links between them. Degree counts the links at a dot, and the handshaking theorem ties all those counts to the number of links. Walks, paths, and cycles describe routes. Connectedness asks whether routes exist at all. Matchings, colorings, and spanning trees each pick out a useful piece of the links. Traversal gives a tree a reading order.
You can now look at a small graph and answer the basic questions without a pause. Five vertices with degrees 3, 3, 2, 2, 2 must have 12/2 = 6 edges. A tree on 8 vertices has 7. A triangle can't be split into two camps, so it needs 3 colors, not 2. Chapter 1 rebuilds this vocabulary with precise notation, and adds the variations that let one skeleton model one-way streets, repeated links, and costs.
Recipes in this chapter
Step-by-step procedures for the problem types this chapter teaches.
One practice set per topic this chapter taught — same fixed, ungraded
ladders as the practice panels inside each section.
Practice: Chapter review: the prerequisite toolkit, all seven ideas at once
(7 problems · doesn’t affect your progress)
You're handed the degree sequence 4, 3, 3, 2, 2, 2 for a graph and asked whether the graph could be bipartite. What should you check first, before attempting any 2-coloring?
Correct! 🎉Not quite.
Right on try — credit.Right — the answer had already been shown, so no credit this time.Next try is worth Answer shown after three tries — this one no longer earns credit.You chose to see the answer — this one earns no credit.
Why
Handshaking is the first sanity check for any degree sequence: 4+3+3+2+2+2=16 is even, so a graph with this sequence can exist at all. That check says nothing about bipartiteness though -- confirming bipartite requires either a working 2-coloring or an odd cycle, not just the degree list.
Apply the handshaking theorem's parity requirement to the degree sum before doing anything else.
Whether the degree sum is even, since handshaking says it must equal twice the edge count
A sequence of vertices in a graph revisits one vertex partway through but never reuses an edge, and it doesn't return to its starting vertex. What is the strongest label -- walk, trail, path, or cycle -- that correctly applies to it?
Correct! 🎉Not quite.
Right on try — credit.Right — the answer had already been shown, so no credit this time.Next try is worth Answer shown after three tries — this one no longer earns credit.You chose to see the answer — this one earns no credit.
Why
No repeated edge rules it in as at least a trail; a path additionally forbids revisiting any vertex, and this sequence does revisit one, so trail is as strong as the label gets. It also never returns to its start, so it isn't a cycle either.
Check the sequence against the trail, path, and cycle definitions in turn, using exactly what it does and doesn't repeat.
Trail
A graph has 9 vertices split across exactly 3 connected components. What is the minimum possible number of edges the whole graph could have?
Correct! 🎉Not quite.
Right on try — credit.Right — the answer had already been shown, so no credit this time.Next try is worth Answer shown after three tries — this one no longer earns credit.You chose to see the answer — this one earns no credit.
Why
Each component needs at least (its own size) minus 1 edges to stay connected, the same n-1 tree fact from the spanning-trees review. Summing that across all 3 components gives 9 - 3 = 6 total, no matter how the 9 vertices are split among the pieces.
Correct answer
Also accepted:
Why
Recall the minimum edge count a single connected piece needs relative to its own vertex count.
Apply that minimum to each of the 3 components separately, then add the three minimums together.
6
A bipartite graph has parts X (5 vertices) and Y (7 vertices). What is the largest a matching in this graph could possibly be?
Correct! 🎉Not quite.
Right on try — credit.Right — the answer had already been shown, so no credit this time.Next try is worth Answer shown after three tries — this one no longer earns credit.You chose to see the answer — this one earns no credit.
Why
Every matched edge uses up one vertex from each side, so a matching can never exceed the size of the smaller part -- here, X's 5 vertices cap any matching at 5 edges, regardless of which specific edges exist.
Think about which side runs out of unmatched vertices first as edges get added to the matching.
5 edges -- a matching can never exceed the smaller side
A graph contains a triangle as a subgraph. What is the minimum possible chromatic number this graph could have?
Correct! 🎉Not quite.
Right on try — credit.Right — the answer had already been shown, so no credit this time.Next try is worth Answer shown after three tries — this one no longer earns credit.You chose to see the answer — this one earns no credit.
Why
Three mutually adjacent vertices force at least 3 colors, since any 2-coloring would give two adjacent triangle vertices the same color -- this lower bound holds no matter how sparse the rest of the graph is.
Correct answer
Also accepted:
Why
Work out how many colors the triangle alone forces, regardless of anything else in the graph.
3
By Cayley's formula, how many distinct labeled trees exist on 4 vertices?
Correct! 🎉Not quite.
Right on try — credit.Right — the answer had already been shown, so no credit this time.Next try is worth Answer shown after three tries — this one no longer earns credit.You chose to see the answer — this one earns no credit.
Why
Cayley's formula gives n^(n-2) labeled trees on n vertices; for n=4, that's 4^2 = 16.
Correct answer
Also accepted:
Why
Identify n=4 here, plug it into Cayley's formula, and simplify the exponent before computing the power.
16
A spanning tree of a connected graph is rooted at an arbitrary vertex and traversed in postorder. Relative to every other vertex, when is the root itself visited?
Correct! 🎉Not quite.
Right on try — credit.Right — the answer had already been shown, so no credit this time.Next try is worth Answer shown after three tries — this one no longer earns credit.You chose to see the answer — this one earns no credit.
Why
Postorder visits a vertex only after all of its subtrees are done; the root's subtrees are the entire rest of the tree, so the root is always the very last vertex postorder records.
Recall postorder's rule for when a vertex is recorded relative to its own subtrees, then apply it to the root, whose subtree is the entire rest of the tree.
Last, only after every other vertex's subtree is fully traversed