Representations — adjacency matrix (space O(V²)), adjacency list (space O(V+E)): Worked examples

Cell	Case class	The degenerate / edge point it probes
C1	Empty graph, $E = 0$	Space still $O (V)$ for the list, still $O (V^{2})$ for the matrix — the "zero input"
C2	Complete (dense) graph, $E = (2 V)$	The maximum edge count; space costs tie
C3	Directed graph	One edge → one list entry, matrix not symmetric
C4	Weighted graph	Cells hold $w$ , absent edge = $\infty$ sentinel
C5	Isolated vertex (degree 0)	Why you cannot drop the $V$ term
C6	Self-loop $(u, u)$	The diagonal cell $A [u] [u]$
C7	Real-world "which representation?"	Compare $E$ vs $V^{2}$ to decide sparse/dense
C8	Exam twist — count walks via $A^{k}$	Matrix power meaning, a limiting/growth behaviour
C9	Multigraph (parallel edges)	Where the plain matrix breaks and the list wins

Worked Examples

Example 1 — The empty graph (Cell C1)

Worked example Statement

A graph has $V = 5$ vertices and no edges at all ( $E = 0$ ). Write both representations and give the exact storage counts.

Forecast: Guess first — does the matrix shrink to nothing because there are no edges? Does the list use zero space?

Step 1 — Build the matrix. Every cell is $0$ : $A = 0000000000000000000000000$ Why this step? The matrix allocates one cell per ordered pair regardless of edges. So it still holds $V^{2} = 5^{2} = 25$ cells, all zero. The "no edges" fact buys you nothing here — that is the whole point of C1.

Step 2 — Build the list.

0 -> []
1 -> []
2 -> []
3 -> []
4 -> []

Why this step? We still allocate the $V = 5$ list headers (one per vertex), each pointing to an empty list. Entries $= 2 E = 0$ , but headers $= 5$ . So list space $= headers + entries = V + 2 E = 5 + 0 = 5$ .

Verify: Matrix cells $= V^{2} = 25$ . ✔ List space $= V + 2 E = 5 + 0 = 5$ . ✔ Neither collapsed to zero — the empty graph proves the matrix pays $O (V^{2})$ and the list pays $O (V)$ even with no edges.

Example 2 — The complete graph (Cell C2)

Worked example Statement

Take the complete undirected graph $K_{4}$ on $V = 4$ vertices — every pair connected. How many edges? Compare matrix space to list space.

Forecast: Guess — for a fully-connected graph, is the list still hugely smaller than the matrix?

Step 1 — Count edges. $E = (2 V) = \frac{V ( V - 1 )}{2} = \frac{4 \cdot 3}{2} = 6$ Why this step? $(2 V)$ is "how many ways to choose 2 distinct vertices" — that is exactly the maximum number of undirected edges (each pair used once). This is the ceiling on $E$ .

Step 2 — Matrix. Every off-diagonal cell is $1$ : $A = 0111101111011110$ Cells $= V^{2} = 16$ . Why this step? Applying the definition $A [u] [v] = 1$ when an edge $u \to v$ exists: in $K_{4}$ every pair is an edge, so every off-diagonal cell is $1$ . The diagonal stays $0$ because $K_{4}$ has no self-loops (a vertex is not joined to itself). The result is symmetric because the graph is undirected.

Step 3 — List space. $V + 2 E = 4 + 2 \cdot 6 = 4 + 12 = 16$ Why this step? Each of the 6 edges lands in two lists → $12$ entries, plus $4$ headers, so list space $=$ headers $+$ entries $= 4 + 12 = 16$ .

Verify: Matrix cells $= 16$ , list space $= 16$ — they tie. ✔ This is exactly the parent's claim: for dense graphs $E = Θ (V^{2})$ so the list loses its space advantage, and the matrix's $O (1)$ edge check makes it the better pick. C2 confirmed.

Example 3 — Directed graph (Cell C3)

Worked example Statement

A directed graph on ${0, 1, 2}$ with arrows $0 \to 1$ , $1 \to 2$ , $2 \to 0$ (a directed cycle). Build both. Is the matrix symmetric?

Forecast: Guess — does the edge $0 \to 1$ also put a $1$ at $A [1] [0]$ ?

The figure draws the three vertices as violet dots with one-way magenta arrows looping $0 \to 1 \to 2 \to 0$ . Notice there is no arrow from $1$ back to $0$ — that missing return arrow is exactly what will make the cell $A [1] [0]$ zero in Step 1, and what breaks symmetry in Step 2. Keep your eye on that gap as you read the matrix.

Step 1 — Matrix. Put a $1$ only in the direction the arrow points: $A = 001100010$ Why this step? Applying the definition, $A [0] [1] = 1$ because the arrow $0 \to 1$ exists (see the figure), but $A [1] [0] = 0$ because there is no arrow back from $1$ to $0$ . For directed graphs $A [u] [v] = 1$ does not force $A [v] [u] = 1$ .

Step 2 — Check symmetry. Compare $A$ with its transpose $A^{T}$ (rows and columns swapped): $A^{T} = 010001100 \neq = A$ Why this step? A matrix is symmetric iff $A = A^{T}$ . Here they differ — precisely because of the missing return arrows in the figure — so the directed matrix is not symmetric. The asymmetry encodes the direction.

Step 3 — List.

0 -> [1]
1 -> [2]
2 -> [0]

Why this step? Directed edge $u \to v$ is stored only in adj[u], never in adj[v]. So entries $= E = 3$ (not $2 E$ ). List space $=$ headers $+$ entries $= V + E = 3 + 3 = 6$ .

Verify: Matrix cells $= V^{2} = 9$ . ✔ List entries $= E = 3$ , list space $= V + E = 6$ . ✔ $A \neq = A^{T}$ . ✔ C3 shows the "one entry, not two" rule for digraphs.

Example 4 — Weighted graph with a missing edge (Cell C4)

Worked example Statement

Undirected weighted graph on ${0, 1, 2}$ : edge ${0, 1}$ weight $5$ , edge ${1, 2}$ weight $2$ . There is no edge ${0, 2}$ . Write both the weighted matrix and the weighted list.

Forecast: Guess — what number goes in the cell for the missing edge ${0, 2}$ ? Zero? Blank?

Step 1 — Fill known edges. Store the weight itself, symmetrically: $A [0] [1] = A [1] [0] = 5, A [1] [2] = A [2] [1] = 2$ Why this step? For a weighted graph the definition replaces the " $1$ " by the actual weight $w (u, v)$ — the cell must record how heavy the edge is, not merely that it exists. Both $A [0] [1]$ and $A [1] [0]$ get $5$ because the graph is undirected, so the edge ${0, 1}$ is usable in both directions with the same weight.

Step 2 — Fill the missing edge with a sentinel. Use $\infty$ : $A = 05 \infty 502 \infty 20$ Why this step? We cannot use $0$ for "no edge", because $0$ is a valid weight (a free road). $\infty$ means "unreachable in one step", which is exactly what shortest-path algorithms like Dijkstra's Algorithm and Floyd-Warshall Algorithm expect: adding $\infty$ to anything stays $\infty$ , so a missing edge never wins as a shortest path. The diagonal is $0$ (distance from a vertex to itself).

Step 3 — The weighted list. Store each neighbour together with its weight as a pair:

0 -> [(1, 5)]
1 -> [(0, 5), (2, 2)]
2 -> [(1, 2)]

Why this step? The list must carry the same information as the matrix, so each entry becomes a pair (neighbour, weight). Note the missing edge ${0, 2}$ simply does not appear — the list stores nothing for absent edges, which is precisely its space advantage. Total edge entries $= 2 E = 4$ .

Verify: The matrix is symmetric — the absent edge is at $A [0] [2] = A [2] [0] = \infty$ , and both stored edges match across the diagonal: $A [0] [1] = A [1] [0] = 5$ and $A [1] [2] = A [2] [1] = 2$ . ✔ List entries $= 2 E = 4$ , so list space $= V + 2 E = 3 + 4 = 7$ . ✔ C4 confirmed: absent $= \infty$ in the matrix and nothing in the list.

Example 5 — Isolated vertex (Cell C5)

Worked example Statement

A graph has $V = 1 0^{6}$ vertices but only one edge, ${0, 1}$ . Vertices $2, 3, \dots$ are all isolated (degree 0). What is the list's space? Is it $O (E)$ ?

Forecast: Guess — since there is basically one edge, is the list nearly free, i.e. $O (1)$ ?

Step 1 — Count edge entries. $E = 1$ , undirected → $2 E = 2$ entries (in adj[0] and adj[1]). Why this step? An undirected edge ${0, 1}$ must be findable from either endpoint, so it is stored twice: once in adj[0] (neighbour $1$ ) and once in adj[1] (neighbour $0$ ). One edge therefore contributes $2$ entries — this is the $2 E$ rule applied to a single edge.

Step 2 — Count headers. We still need one list header for every vertex, including the $1 0^{6} - 2$ isolated ones: $headers = V = 1 0^{6}$ Why this step? An isolated vertex still exists and must be indexable — adj[999999] must return an (empty) list, so its header is allocated. You cannot skip it.

Step 3 — Total. $list space = headers + entries = V + 2 E = 1 0^{6} + 2 = 1000002 \approx 1 0^{6}$ Why this step? The $V$ term dominates. If you had claimed the list is $O (E) = O (1)$ you would be off by a factor of a million.

Verify: List space $= V + 2 E = 1000000 + 2 = 1000002$ . ✔ This is why the parent insists on $O (V + E)$ , never $O (E)$ . See Big-O Notation for why the dominant $V$ term is what we report. C5 confirmed.

Example 6 — Self-loop (Cell C6)

Worked example Statement

A directed graph on ${0, 1}$ has edges $0 \to 1$ and a self-loop $0 \to 0$ . Build the matrix and the list.

Forecast: Guess — where does the self-loop show up in the matrix?

Step 1 — Matrix. The self-loop sets the diagonal cell: $A = (1010)$ Why this step? $A [0] [0] = 1$ records the loop $0 \to 0$ ; $A [0] [1] = 1$ records $0 \to 1$ . Normally the diagonal is $0$ ("no vertex is its own neighbor"), but a self-loop is precisely the exception that turns a diagonal cell on.

Step 2 — List.

0 -> [0, 1]
1 -> []

Why this step? Vertex $0$ 's neighbor list contains itself, so adj[0] includes 0. Each directed edge (including the self-loop) adds exactly one entry.

Verify (matrix): The trace of $A$ — meaning the sum of its diagonal entries $A [0] [0] + A [1] [1]$ (the cells where row index equals column index) — is $1 + 0 = 1$ , exactly the number of self-loops. ✔ Total matrix cells $= V^{2} = 4$ . ✔

Verify (list): This is a directed graph with $E = 2$ edges ( $0 \to 0$ and $0 \to 1$ ), so entries $= E = 2$ (adj[0] holds 0 and 1; adj[1] is empty). List space $=$ headers $+$ entries $= V + E = 2 + 2 = 4$ . ✔ C6 confirmed: self-loops live on the diagonal, and each contributes one directed list entry.

Example 7 — Real-world "which representation?" (Cell C7)

Worked example Statement

You store a road map: $V = 2 \times 1 0^{5}$ intersections, each connected to about $4$ others (roads). So $E \approx \frac{1}{2} \cdot V \cdot 4 = 4 \times 1 0^{5}$ . Matrix or list?

Forecast: Guess — with hundreds of thousands of vertices, is a $V \times V$ grid affordable?

Step 1 — Matrix cost. $V^{2} = (2 \times 1 0^{5})^{2} = 4 \times 1 0^{10} cells$ Why this step? That is 40 billion cells — tens of gigabytes. Impossible for a laptop.

Step 2 — List cost. $list space = V + 2 E = 2 \times 1 0^{5} + 2 \cdot 4 \times 1 0^{5} = 2 \times 1 0^{5} + 8 \times 1 0^{5} = 1 0^{6} slots$ Why this step? A million slots (headers plus entries) is trivial (a few MB).

Step 3 — Sparse test. Ratio of actual to possible edges: $\frac{E}{( 2 V )} \approx \frac{4 \times 1 0 ^{5}}{2 \times 1 0 ^{10}} = 2 \times 1 0^{- 5}$ Why this step? Edges are $0.002%$ of possible pairs → overwhelmingly sparse → the list wins. Traversals like Breadth-First Search (BFS) and Depth-First Search (DFS) then run in $O (V + E) = O (1 0^{6})$ , not $O (V^{2}) = O (4 \times 1 0^{10})$ .

Verify: $V^{2} = 4 \times 1 0^{10}$ . ✔ $V + 2 E = 1 0^{6}$ . ✔ Sparsity ratio $= 2 \times 1 0^{- 5}$ . ✔ C7 confirmed: compare $E$ to $V^{2}$ , choose list when sparse.

Example 8 — Exam twist: count walks with $A^{k}$ (Cell C8)

Worked example Statement

Undirected triangle: vertices ${0, 1, 2}$ all mutually connected ( $K_{3}$ ). Using the matrix, count the number of walks of length 2 from vertex $0$ back to vertex $0$ .

Forecast: Guess — how many 2-step round trips start and end at $0$ ? Is it $1$ , $2$ , or $3$ ?

The figure shows the triangle $K_{3}$ with its three plain navy edges, then overlays the two highlighted round trips out of vertex $0$ : the magenta path $0 \to 1 \to 0$ and the orange path $0 \to 2 \to 0$ . Count the coloured round trips in the picture — there are exactly two — and that is the number Step 2 will compute as $(A^{2}) [0] [0]$ . The figure is the answer drawn out before we do the algebra.

Step 1 — Write $A$ . $A = 011101110$ Why this step? This is just the adjacency matrix of $K_{3}$ from the definition: $A [u] [v] = 1$ whenever $u$ and $v$ are joined. Every off-diagonal cell is $1$ (all three pairs are edges) and the diagonal is $0$ (no self-loops). We need $A$ explicitly because the walk-count trick works by multiplying $A$ by itself, so we must have the exact grid in hand before any multiplication.

Step 2 — Square it via Matrix Multiplication. The entry $(A^{2}) [0] [0]$ sums over the middle vertex $m$ : $(A^{2}) [0] [0] = \sum_{m} A [0] [m] A [m] [0] = A [0] [0]^{2} + A [0] [1] A [1] [0] + A [0] [2] A [2] [0]$ $= 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 1 = 2$ Why this step? Each term $A [0] [m] A [m] [0]$ is $1$ only when $0$ can step to $m$ and $m$ can step back to $0$ — i.e. a genuine 2-step walk $0 \to m \to 0$ . Summing over all $m$ counts them all. That is exactly why matrix multiplication counts walks. Match the two nonzero terms to the two coloured paths in the figure.

Step 3 — Full square (sanity). Compute every entry the same way: $A^{2} = 211121112$ Why this step? The diagonal $2$ s = two 2-walks back home (via each of the other two vertices); the off-diagonal $1$ s = one 2-walk between distinct vertices (via the single third vertex). Doing the full square confirms our single-cell answer is not a fluke and shows the pattern.

Verify: $(A^{2}) [0] [0] = 2$ : the two walks are $0 \to 1 \to 0$ and $0 \to 2 \to 0$ . ✔ Full $A^{2}$ has diagonal $2$ and off-diagonal $1$ . ✔ C8 confirmed: $(A^{k}) [u] [v]$ counts length- $k$ walks.

Example 9 — Multigraph: where the plain matrix breaks (Cell C9)

Worked example Statement

Two cities ${0, 1}$ joined by three parallel roads (a multigraph — the same pair of vertices has more than one edge between them). Can a plain $0/1$ adjacency matrix store this? What about the list?

Forecast: Guess — can a single matrix cell hold "three edges"?

Step 1 — Try the plain matrix. The cell $A [0] [1]$ is a boolean $1$ = "at least one edge". It cannot distinguish 1 road from 3: $A = (0110) (loses the count!)$ Why this step? The plain matrix definition maps "edge exists" → $1$ . Three parallel edges all collapse to the same single $1$ , so the multiplicity is destroyed — from this matrix you can never recover that there were three roads. This is the concrete way the plain matrix fails for multigraphs.

Step 2 — Fix it: upgrade the cell to an integer count. $A = (0330)$ Why this step? We change the cell's type from boolean to integer so it stores how many parallel edges. Now $A [0] [1] = 3$ records all three roads and the matrix survives — but only after this deliberate upgrade, which the plain definition did not give us for free.

Step 3 — The list handles it naturally. Just append the neighbour once per edge:

0 -> [1, 1, 1]
1 -> [0, 0, 0]

Why this step? The list appends one entry per edge, so three roads → three entries in each endpoint's list. No type change, no special case — the list represents multiplicity for free, which is why the list wins on multigraphs.

Verify (matrix): The integer-count matrix stores the multiplicity $A [0] [1] = 3$ , while the plain boolean matrix would store only $1$ (and $3 \neq = 1$ , so the plain form genuinely loses information). ✔

Verify (list): adj[0] has length $3$ ; with $E = 3$ undirected edges, entries $= 2 E = 6$ , so list space $= V + 2 E = 2 + 6 = 8$ . ✔ C9 confirmed: the plain boolean matrix loses parallel edges; the integer matrix or the list keeps them.

Coverage check

Recall Did we hit every cell?

Match each example to its cell — hide and recall.

Example 1 covers which cell? ::: C1 — empty graph, $E = 0$ Example 2 covers which cell? ::: C2 — complete/dense, space tie Example 3 covers which cell? ::: C3 — directed, matrix not symmetric Example 4 covers which cell? ::: C4 — weighted, missing edge $= \infty$ Example 5 covers which cell? ::: C5 — isolated vertex, cannot drop $V$ Example 6 covers which cell? ::: C6 — self-loop on the diagonal Example 7 covers which cell? ::: C7 — real-world sparse road map, pick list Example 8 covers which cell? ::: C8 — $A^{k}$ counts walks Example 9 covers which cell? ::: C9 — multigraph breaks the boolean matrix

Back to the parent overview.

Worked examples — Representations — adjacency matrix (space O(V²)), adjacency list (space O(V+E))

The scenario matrix

Worked Examples

Example 1 — The empty graph (Cell C1)

Example 2 — The complete graph (Cell C2)

Example 3 — Directed graph (Cell C3)

Example 4 — Weighted graph with a missing edge (Cell C4)

Example 5 — Isolated vertex (Cell C5)

Example 6 — Self-loop (Cell C6)

Example 7 — Real-world "which representation?" (Cell C7)

Example 8 — Exam twist: count walks with $A^{k}$ (Cell C8)

Example 9 — Multigraph: where the plain matrix breaks (Cell C9)

Coverage check