i. Graph Basics and Modeling

The hard part of most graph problems is building the right graph: what is a vertex (often a state), what is an edge (a move), which weights. This note collects representations, standard modelling tricks, reductions to known problems, the basic counting facts with proofs, and a selection table for algorithms in this chapter.

What makes a model correct. A graph model (or a reduction to a known graph problem) is correct exactly when there is a structure-preserving correspondence between the objects the original problem asks about and the objects the graph problem answers: every valid solution of the original problem maps to a walk/path/cut/matching etc. of the same cost in the graph, and conversely every such structure in the graph maps back to a valid solution of the same cost. Both directions matter — a construction that only shows “every original solution gives a graph solution” can still be wrong if some graph solution corresponds to nothing valid in the original problem (a classic bug: forgetting a constraint when building the graph lets the algorithm find a cheaper-looking but infeasible answer). Every row in the modelling and reductions tables below is this same correspondence argument specialised to one shape; when building a new model, state both directions explicitly rather than checking only that the construction “looks right” on the sample input.

Representations

Representation	Memory	Edge lookup	Iterate neighbours	Good for
adjacency list vector<vector<int>>	$O(n+m)$	$O(\mathrm{deg}v)$	$O(\mathrm{deg}v)$	default: DFS, BFS, Dijkstra, flows
CSR (offsets + flat array)	$O(n+m)$	$O(\mathrm{deg}v)$	$O(\mathrm{deg}v)$	2–3× faster traversals on $10^6$+ edges, no pointer chase
adjacency matrix	$O(n^2)$	$O(1)$	$O(n)$	Floyd–Warshall, dense Prim/Dijkstra $O(n^2)$, $n\le 5000$
bitset<N> rows	$n^2/8$ bytes	$O(1)$	$O(n/64)$	neighbourhood intersections: triangles, cliques, transitive closure in $O(n^3/64)$
edge list	$O(m)$	$O(m)$	$O(m)$	Kruskal, Bellman–Ford, offline processing
implicit (neighbour function)	$O(1)$	—	$O(\text{branching})$	grids, puzzles, number states — the vertices are states, the edges are moves, and the adjacency list is never built; recognise it whenever a problem asks for the minimum number of (reversible, cheaply-enumerable) operations to transform one state into another

// CSR from an edge list (directed u -> v)
vector<int> start(n + 1), to(m);
for (auto [u, v] : edges) start[u + 1]++;
for (int i = 0; i < n; i++) start[i + 1] += start[i];
vector<int> pos(start.begin(), start.end() - 1);
for (auto [u, v] : edges) to[pos[u]++] = v;               // neighbours of u: to[start[u] .. start[u+1])

Modelling tricks

Situation	Construction
movement depends on carried state (keys, fuel, parity, time mod $k$, “used the coupon”)	vertices $(v,s)$: layered / product graph
vertex capacities, vertex costs, vertex-disjoint paths	split $v$ into $v_{\text{in}}\to v_{\text{out}}$
“minimum number of edge reversals”	forward edge weight 0, reversed edge weight 1, 0-1 BFS
teleports between all cells of a colour / all multiples / all vertices in a range	one virtual vertex per group (edges in 0 and out with the cost), or a segment tree of virtual vertices (Shortest Path Techniques)
dense graph whose complement is sparse	BFS on the complement with an unvisited list (BFS and DFS)
constraints $x_j-x_i\le c$	difference constraints, shortest paths
two choices per item, pairwise conflicts	2-SAT (2-SAT)
“after time $t$ the edge disappears”	process edges in time order, reverse time, or segment tree over time
huge number line with few interesting points	compress to the interesting points plus edges between consecutive ones
cost depends on the previous edge (turn penalties)	vertices = directed edges (line graph)
path must visit a small set of special vertices in some order	shortest paths between specials + bitmask DP
who must come before whom	topological order on a DAG (Topological Sort)
cost grows with how much of an edge’s capacity you use, convexly	subdivide the edge into several parallel edges of increasing cost; min-cost flow picks the cheapest first (Min-Cost Flow)

Common carried states for the layered-graph row above: keys collected $\to (v,\text{mask})$; fuel remaining $\to (v,f)$; moves used mod $k$ $\to (v,t\mathrm{mod}k)$; one-time teleport used $\to (v,0/1)$; current speed or direction $\to (v,d)$. The graph grows by the number of states; the algorithm is unchanged.

Reductions worth knowing

Problem	Becomes
min path cover of a DAG (vertex-disjoint)	$n$ − max bipartite matching (out-copies × in-copies)
min path cover allowing shared vertices	transitive closure, then the above
max antichain of a poset	Dilworth: min chain cover (Matching)
bipartite min vertex cover / max independent set	König: matching / $n$ − matching
max weight closure (project selection)	min cut
binary labelling with pairwise penalties (submodular)	min cut
$k$ edge-disjoint / vertex-disjoint paths	max flow (split vertices)
shortest pair of disjoint paths	min-cost flow of 2 (Suurballe)
traverse every edge at least once	Chinese postman: matching on odd vertices
bottleneck path (maximise the minimum edge)	path in the maximum spanning tree, or binary search + BFS
reachability with cycles	condense SCCs, then DAG DP
minimum mean cycle	Karp’s algorithm or binary search + negative cycle

Taxonomy and named graphs

Axis	Values
direction	undirected ($(u,v)$ implies $(v,u)$) vs. directed (digraph)
weights	unweighted (every edge costs 1) vs. weighted
edge rules	simple (no loops/parallel edges) vs. multigraph (parallel edges) vs. pseudograph (loops and parallel edges)
connectivity	connected vs. disconnected (components); a component is a maximal connected subgraph
rooting	out-tree / arborescence (edges point away from the root) vs. in-tree / anti-arborescence (edges point toward it)

Named graphs worth recognising on sight: DAG (no directed cycle, has a topological order, at least one source and sink); $K_{m,n}$ (complete bipartite, $mn$ edges); $P_n$ (path, two degree-1 vertices); $K_{1,n-1}$ (star); wheel $W_n$ (cycle plus a universal centre); hypercube $Q_d$ ($d$-bit strings, adjacent iff Hamming distance 1, $2^d$ vertices, $d{2}^{d-1}$ edges, $d$-regular); tournament (an orientation of $K_n$, exactly one directed edge per pair — see Special Graph Classes for the king-vertex theorem); complement $\overline{G}$ (same vertices, adjacency inverted); line graph (one vertex per edge of $G$, adjacent iff they share an endpoint); caterpillar (a tree that becomes a path once leaves are removed); chordal (every cycle of length $\ge 4$ has a chord); planar (drawable with no edge crossings, see the Euler’s-formula bounds below); Eulerian (a closed walk using every edge exactly once; connected with all degrees even, see Eulerian Paths); semi-Eulerian (Eulerian path but not cycle: exactly two odd-degree vertices); Hamiltonian (a cycle visiting every vertex once — no known polynomial characterisation, deciding it is NP-complete); semi-Hamiltonian (Hamiltonian path but perhaps no cycle).

Recognising the graph in a statement

A more basic pass than the modelling table above — the phrasing alone often names the problem type directly:

Phrasing	Vertices	Edges / problem
”minimum number of operations to transform X into Y”	states	one operation $\to$ BFS
”can we reach this configuration”	configurations	one move $\to$ reachability
”these two cannot both be chosen”	choices	conflict $\to$ 2-SAT or bipartite
”assign each A to a B”	A’s and B’s	compatibility $\to$ matching
”minimum cost to separate / block”	as given	min cut
”maximum number of disjoint routes”	as given	max flow
”connect everything cheaply”	as given	MST
”cheapest route”	as given	shortest path

Basic facts

Fact	Statement
handshake lemma	${\sum }_v\mathrm{deg}v=2m$; the number of odd-degree vertices is even
trees	for $n$ vertices, any two of {connected, acyclic, $m=n-1$} imply the third
forests	$m=n-c$ for $c$ components
bipartite	iff no odd cycle (Bipartite)
Euler’s formula	connected plane graph: $V-E+F=2$ (with $C$ components: $V-E+F=1+C$)
planar density	$E\le 3V-6$ for $V\ge 3$; $E\le 2V-4$ if triangle-free; so $K_5$, $K_{3,3}$ are not planar
planar degeneracy	every planar graph has a vertex of degree $\le 5$ (so 6-colourable greedily; 5 by Kempe chains, 4 by the four colour theorem)
Mantel / Turán	triangle-free graphs have $\le \lfloor n^2/4\rfloor$ edges; $K_{r+1}$-free at most $(1-\frac{1}{r})\frac{n^2}{2}$
triangles	at most $O(m\sqrt{m})$ triangles, all listed in $O(m\sqrt{m})$ by orienting edges by degree (Sqrt)

Proof: handshake, trees, Euler's formula and the planar bounds

Handshake: every edge contributes 1 to the degree of each endpoint, so the degree sum counts edges twice; an even sum has an even number of odd terms.
Trees: adding the edges of a graph one by one to an empty graph on $n$ vertices, each edge either merges two components (count drops by 1) or closes a cycle. Acyclic means every edge merges, so $c=n-m$; connected means $c=1$. Hence acyclic + connected gives $m=n-1$; acyclic + $m=n-1$ gives $c=1$; connected + $m=n-1$ means $n-1$ edges reduced $n$ components to 1, so every edge merged and none closed a cycle.
Euler: induction on $E$. A tree has $E=V-1$ and one face. Otherwise some edge lies on a cycle; it separates two different faces, so deleting it removes one edge and one face and keeps $V-E+F$.
Planar bounds: in a simple connected plane graph with $V\ge 3$, every face is bounded by at least 3 edge sides and every edge has 2 sides, so $3F\le 2E$. Substituting $F=2-V+E$ gives $E\le 3V-6$; with girth $\ge 4$, $4F\le 2E$ gives $E\le 2V-4$. $K_5$ has $10>9$ edges and $K_{3,3}$ (bipartite, triangle-free) has $9>8$. Average degree $2E/V<6$ gives a vertex of degree $\le 5$.
Mantel: for adjacent $u,v$ in a triangle-free graph the neighbourhoods are disjoint, so $\mathrm{deg}u+\mathrm{deg}v\le n$; summing over edges, ${\sum }_v\mathrm{deg}(v{)}^2\le mn$, and Cauchy–Schwarz $\sum {\mathrm{deg}}^2\ge (2m{)}^2/n$ gives $m\le n^2/4$.

Choosing an algorithm

Task	Default	Note
unweighted shortest paths	BFS	$O(n+m)$
0/1 weights	0-1 BFS	deque
nonnegative weights	Dijkstra with a binary heap	$O(m\log n)$; dense: $O(n^2)$ array version
negative weights	Bellman–Ford / SPFA	$O(nm)$; detect negative cycles
DAG	topological order DP	negatives fine, also longest paths
all pairs	Floyd–Warshall $O(n^3)$, or Johnson $O(nm\log n)$
connectivity under insertions	DSU
connectivity with deletions	offline segment tree over time + rollback DSU; online HDT
strongly connected / 2-SAT	Tarjan or Kosaraju
bridges, articulation points, BCC	lowlink DFS
MST	Kruskal $O(m\log m)$; Prim $O(n^2)$ dense; Borůvka for implicit graphs
max flow	Dinic	push–relabel for dense/hard cases
bipartite matching	Hopcroft–Karp (or Dinic)
general matching	blossom / Tutte matrix rank
min-cost flow	SSP with potentials
NP-hard (Hamiltonian, clique, colouring)	bitmask DP / branch and bound for $n\le 20$–$100$

Before coding: directed or undirected? self-loops and multi-edges? connected? negative weights? the sentinel for “unreachable”? is recursion depth safe (paths of length $10^6$)? does $n$ actually fit the algorithm ($O(V^3)$ needs $V\lesssim 500$, $O(2^V)$ needs $V\lesssim 22$)?

Terminology

Term	Meaning
Adjacent vertices	joined by an edge
Incident edge	an edge touching a given vertex
Path / path length	a sequence of vertices with consecutive ones adjacent / its number of edges
Simple path	no repeated vertex
Cycle	a path returning to its start with no repeated interior vertex
Leaf / pendant	degree 1
Isolated vertex	degree 0
Bridge (cut edge)	removing it increases the component count
Articulation point (cut vertex)	removing it increases the component count
Subgraph / spanning subgraph	a subset of vertices and edges / one containing all vertices
Spanning tree	a spanning subgraph that is a tree