Graph Representations & Terminology

Graph Theory

Chapter 2 · Graph Representations & Terminology

Chapter 1 showed the space gap between two representations in the abstract. This chapter builds both, in full, for the exact same small graph — and pins down the vocabulary every later chapter leans on.

Core Terminology

Term	Meaning
Vertex (node)	A single "thing" in the graph
Edge	A connection between two vertices
Degree	The number of edges touching a given vertex
Directed edge	A one-way connection, `u → v` — an asymmetric relation, in Discrete Mathematics Fundamentals Chapter 5's own terms
Undirected edge	A two-way connection, `u — v` — a symmetric relation
Weighted edge	An edge carrying a numeric cost (distance, time, capacity)
Path	A sequence of edges connecting one vertex to another

A Worked Example: One Graph, Two Representations

Five vertices, five undirected, unweighted edges: A-B, A-C, B-C, C-D, D-E.

Adjacency Matrix

     A  B  C  D  E
A  [0, 1, 1, 0, 0]
B  [1, 0, 1, 0, 0]
C  [1, 1, 0, 1, 0]
D  [0, 0, 1, 0, 1]
E  [0, 0, 0, 1, 0]

Adjacency List

A: [B, C]
B: [A, C]
C: [A, B, D]
D: [C, E]
E: [D]

Reading degree directly off the adjacency list (its own length per vertex): degree(A)=2, degree(B)=2, degree(C)=3, degree(D)=2, degree(E)=1. For this graph, V=5, E=5: matrix needs 25 cells, the list needs 15 entries — a smaller gap than Chapter 1's own 1,000-vertex example, since the space advantage of the list grows with graph size.

The Time/Space Tradeoff

The same tradeoff Algorithms & Complexity Chapter 8 already established

Just as that chapter found merge sort's better time came with a real space cost against bubble sort, these two graph representations trade space for a different operation's speed — neither is simply "better."

Operation	Adjacency matrix	Adjacency list
Space	O(V²)	O(V+E)
Check if edge (u,v) exists	O(1) — direct lookup	O(degree(v)) — must scan the list
List all neighbors of v	O(V) — scan the whole row	O(degree(v)) — already just that list
Add a new vertex	O(V²) — matrix must grow in both dimensions	O(1) — just add a new empty list

When each representation actually wins

For sparse graphs (E much smaller than V², the overwhelmingly common real-world case — social networks, road networks, dependency graphs), the adjacency list wins on both space and the neighbor-listing operations traversal algorithms need most. The matrix only pulls ahead for dense graphs (E close to V²) or when "does this specific edge exist" needs to be checked very frequently, where its O(1) lookup genuinely matters more than the space cost.

Representations in Code

vertices = ['A', 'B', 'C', 'D', 'E']
edges = [('A','B'), ('A','C'), ('B','C'), ('C','D'), ('D','E')]

# Adjacency list — the standard choice for sparse graphs
adj_list = {v: [] for v in vertices}
for u, v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u)  # undirected: add both directions

print(adj_list['C'])           # ['A', 'B', 'D']
print(len(adj_list['C']))     # 3 -- degree(C)

Hands-On Exercises

Exercise 1

Build the adjacency matrix and adjacency list for the undirected graph with vertices {P, Q, R, S} and edges P-Q, P-R, Q-R, R-S. State the degree of each vertex.

📄 View solution

Exercise 2

A graph has 200 vertices and 190 edges (a sparse graph). Compute the adjacency matrix space (V²) and the adjacency list space (V+2E). Which representation would you choose for this graph, and why, using this chapter's own sparse-vs-dense reasoning?

📄 View solution

Exercise 3

A system needs to check, very frequently, whether a specific pair of users is directly connected — but rarely needs to list all of a user's connections. Using this chapter's own time/space tradeoff table, explain which representation better fits this specific access pattern, even if the underlying social graph is sparse.

📄 View solution

Chapter 2 Quick Reference

Vertex, edge, degree — the core vocabulary; directed edges are asymmetric relations, undirected are symmetric (Discrete Mathematics Fundamentals Chapter 5)
Adjacency matrix: O(V²) space, O(1) edge lookup, O(V) to list neighbors
Adjacency list: O(V+E) space, O(degree) edge lookup, O(degree) to list neighbors
Sparse graphs (the common real-world case) favor the list on nearly every dimension; dense graphs or frequent-edge-lookup workloads favor the matrix
This is the same time/space tradeoff pattern Algorithms & Complexity Chapter 8 already established for sorting algorithms, now applied to graph storage
Next chapter: Graph traversal — BFS and DFS