Chapter 7: Graphs

A graph $G = (V, E)$ has $|V| = n$ vertices and $|E| = m$ edges. In an undirected graph, each edge $\{u, v\}$ contributes $1$ to both $\deg(u)$ and $\deg(v)$, giving the handshaking lemma $\sum_{v \in V} \deg(v) = 2|E|$. In a directed graph, $\sum_v \deg^+(v) = \sum_v \deg^-(v) = |E|$. The maximum edge count is $\binom{n}{2} = \frac{n(n-1)}{2}$ for a simple undirected graph (complete graph $K_n$) or $n(n-1)$ for a directed one. Sparse graphs have $m = O(n)$; dense graphs have $m = \Theta(n^2)$.

An adjacency list stores $n$ vertex entries, each mapping to a list of neighbors. Total space is $O(n + m)$: each vertex contributes $O(1)$ overhead, and each edge appears in 1 or 2 lists (directed or undirected). Checking whether edge $(u, v)$ exists requires scanning $u$'s neighbor list — $O(\deg(u))$ worst case. Iterating all neighbors of $u$ is $O(\deg(u))$, which is optimal. For sparse graphs with $m = O(n)$, total space is $O(n)$, making adjacency lists dramatically more efficient than matrices.

An $n \times n$ adjacency matrix $A$ has $A[i][j] = 1$ if edge $(i, j)$ exists. Space is always $O(n^2)$ regardless of $m$. Edge existence queries are $O(1)$, but iterating the neighbors of vertex $i$ is $O(n)$ — you must scan the entire row. The matrix is symmetric ($A = A^T$) for undirected graphs. Matrix powers have elegant meaning: $A^k[i][j]$ counts walks of length $k$ from $i$ to $j$. For dense graphs with $m = \Theta(n^2)$, matrices and lists use the same space, but matrices give $O(1)$ edge lookups.