Chapter 1
Graphs and Models
Most graph problems are won or lost at modelling: deciding what the vertices *are*. This chapter builds the vocabulary that the rest of the book assumes, and the two representations you will type in a contest.
7 pages4,107 words18 problems1 interactive
1What a Graph Is, and How to Notice OneVertices, edges, and the modelling habit that turns a scary statement into a graph problem.2A Zoo of GraphsThe named families you should recognise on sight — and the edge counts each one gives you for free.3Four Ways to Store a GraphAdjacency list, matrix, edge list, and the compressed variants — with the memory and time each one really costs.4Walks, Trails, Paths, CyclesFour words that decide whether your algorithm is linear or exponential — plus the cycle-removal lemma.5Subgraphs, Minors and OperationsInduced vs. not, contraction, complement — the operations that turn proofs into algorithms.6Connectivity, Bridges, Articulation PointsWhat it means for a graph to hold together, and the two linear-time tests for its weakest points.7Bipartite Graphs and 2-ColouringThe odd-cycle theorem, the BFS that finds it, and why half of all "is this possible?" problems are secretly bipartite.