A drawing is a great way for a human to understand a graph, but a computer needs the graph as data: numbers in a matrix or entries in lists. The way you store a graph decides how fast your algorithms run and how much memory they use, which is why "adjacency matrix or adjacency list?" is a standard interview question.
The second half of this chapter tackles a deeper question: two graphs can look completely different on paper and still be the same graph with the vertices renamed. This idea is called isomorphism. We will learn how to prove two graphs are isomorphic (find the renaming) and how to prove they are not (find a property one has and the other lacks). We use the vocabulary from Graph Theory Basics throughout.
Simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic, written G1 ≅ G2, if there is a bijection f : V1 → V2 such that for all u, v ∈ V1: u and v are adjacent in G1 if and only if f(u) and f(v) are adjacent in G2.
A Running Example
We will represent this graph G in four ways. It has 5 vertices and 6 edges: a square a–b–c–d with the diagonal a–c, plus a pendant vertex e attached to c.
a ─────── b
│ ╲ │
│ ╲ │
│ ╲ │
d ─────── c ─────── e
Edges: e1 = ab, e2 = bc, e3 = cd, e4 = da, e5 = ac, e6 = ce
Degrees: a 3, b 2, c 4, d 2, e 1 (sum 12 = 2 × 6)
1. Adjacency Matrix
For a graph with vertices v1, …, vn, the adjacency matrix A is the n × n matrix with aij = 1 if vi and vj are adjacent and aij = 0 otherwise.
a b c d e
a [ 0 1 1 1 0 ]
b [ 1 0 1 0 0 ]
c [ 1 1 0 1 1 ]
d [ 1 0 1 0 0 ]
e [ 0 0 1 0 0 ]
Properties worth remembering:
For an undirected graph A is symmetric (aij = aji). For a simple graph the diagonal is all 0 (no loops).
The sum of row i is deg(vi). The sum of all entries is 2|E|.
For a multigraph, aij is the number of edges between vi and vj. A loop is usually recorded as 1 on the diagonal (some books write 2 so that row sums still give degrees; check which convention your course uses).
For a digraph, aij = 1 when there is an edge from vi to vj. A need not be symmetric; row sums are out-degrees and column sums are in-degrees.
The matrix depends on the order in which you list the vertices. Reordering the vertices permutes the rows and the columns in the same way.
Powers of A count walks
Theorem. For every k ≥ 1, the (i, j) entry of Ak equals the number of walks of length k from vi to vj.
Proof (induction on k). For k = 1, aij is the number of walks of length 1 (single edges) from vi to vj. Assume the claim for k. A walk of length k + 1 from vi to vj is a walk of length k from vi to some vertex vl, followed by an edge from vl to vj. Summing over l, the number of such walks is ∑l (Ak)il · alj, which is exactly the (i, j) entry of Ak · A = Ak+1. ∎
For our graph:
a b c d e a b c d e
A² = a [ 3 1 2 1 1 ] A³ = a [ 4 5 6 5 2 ]
b [ 1 2 1 2 1 ] b [ 5 2 6 2 1 ]
c [ 2 1 4 1 0 ] c [ 6 6 4 6 4 ]
d [ 1 2 1 2 1 ] d [ 5 2 6 2 1 ]
e [ 1 1 0 1 1 ] e [ 2 1 4 1 0 ]
(A²)ac = 2: the walks a–b–c and a–d–c.
The diagonal of A² gives degrees: (A²)ii = deg(vi), because a closed walk of length 2 goes out along an edge and straight back. So trace(A²) = 2|E| = 12.
(A³)aa = 4: the closed walks a–b–c–a, a–c–b–a, a–c–d–a, a–d–c–a. Each triangle through a is traversed in two directions.
Each triangle gives 6 closed walks of length 3 (3 starting vertices × 2 directions), so number of triangles = trace(A³)/6 = 12/6 = 2 (triangles abc and acd).
2. Incidence Matrix
For a graph with vertices v1, …, vn and edges e1, …, em, the incidence matrix M is the n × m matrix with mij = 1 if edge ej is incident with vi, and 0 otherwise.
e1 e2 e3 e4 e5 e6
ab bc cd da ac ce
a [ 1 0 0 1 1 0 ]
b [ 1 1 0 0 0 0 ]
c [ 0 1 1 0 1 1 ]
d [ 0 0 1 1 0 0 ]
e [ 0 0 0 0 0 1 ]
In a loop-free graph every column has exactly two 1s (the two ends of the edge), so the sum of all entries is 2|E| again. (With this 0/1 convention a loop column has a single 1.)
Row sums are degrees (for loop-free graphs).
Multiple edges give identical columns.
For a digraph, a common convention writes +1 at the tail and −1 at the head of each edge.
Incidence matrices are used in network flow and circuit theory (Kirchhoff's laws) but rarely in everyday programming, because an n × m matrix is even larger than an adjacency matrix.
3. Adjacency List
Store, for each vertex, a list (or set) of its neighbours:
a : b, c, d
b : a, c
c : a, b, d, e
d : a, c
e : c
The total length of all lists is 2|E| for an undirected graph (each edge appears in both endpoints' lists) and |E| for a digraph. This is what vector<vector<int>> in C++ or a dict of lists in Python usually holds, and what BFS and DFS use.
4. Edge List
Simply list the edges: (a,b), (b,c), (c,d), (d,a), (a,c), (c,e). It takes O(|E|) space and is the natural input format for algorithms that process edges in sorted order, such as Kruskal's minimum spanning tree algorithm.
Comparing the Representations
Let n = |V| and m = |E|.
Operation | Adjacency matrix | Adjacency list | Edge list |
|---|---|---|---|
Space | Θ(n²) | Θ(n + m) | Θ(m) |
Is uv an edge? | O(1) | O(deg(u)) (O(1) expected with hash sets) | O(m) |
List neighbours of u | O(n) | O(deg(u)) | O(m) |
Add an edge | O(1) | O(1) | O(1) |
BFS / DFS of whole graph | O(n²) | O(n + m) | O(n · m) unless converted to lists first |
Best for | Dense graphs, fast edge tests, matrix methods (walk counting, Floyd–Warshall) | Sparse graphs, traversals, most real networks | Sorting edges by weight |
A graph is sparse when m is much smaller than n² (road networks, social networks, the web) and dense when m is close to n². Most real graphs are sparse: a social network with a billion users has nowhere near 1018 friendships, so an adjacency matrix would be hopeless.
Graph Isomorphism
Look at these two graphs:
G1: 1 ─── 2 G2: p ─── q
│ ╲ │ │ ╱ │
│ ╲ │ │ ╱ │
4 ─── 3 s ─── r
edges 12, 23, 34, 41, 13 edges pq, qr, rs, sp, qs
Both are a 4-cycle plus one diagonal. The diagonal joins the two degree-3 vertices (1 and 3 in G1; q and s in G2). So map degree-3 vertices to degree-3 vertices: f(1) = q, f(3) = s, f(2) = p, f(4) = r. Check every edge:
12 → qp ✓ 23 → ps ✓ 34 → sr ✓ 41 → rq ✓ 13 → qs ✓
All 5 edges map to edges, f is a bijection and both graphs have 5 edges, so non-edges also map to non-edges. Hence G1 ≅ G2.
In matrix language: G1 ≅ G2 exactly when there is a permutation matrix P with A2 = P A1 PT, i.e. when reordering the vertices of G1 turns its adjacency matrix into that of G2.
Invariants: how to prove two graphs are NOT isomorphic
An invariant is a property that isomorphic graphs always share. If two graphs differ in any invariant, they are not isomorphic.
Number of vertices and number of edges.
Degree sequence.
Number of cycles of each length (in particular, the number of triangles).
Connectedness and the number of components; existence of cut vertices or bridges.
Being bipartite or being regular.
The degrees of the neighbours of each vertex (a degree-3 vertex adjacent to two leaves must map to a degree-3 vertex adjacent to two leaves).
The complements: G1 ≅ G2 if and only if Ḡ1 ≅ Ḡ2. For dense graphs it is often easier to compare complements.
The catch: matching invariants never prove isomorphism. Equal degree sequences are necessary but not sufficient.
Example: same degree sequence, not isomorphic
The triangular prism and K3,3. Both have 6 vertices, 9 edges and are 3-regular, so the degree sequences agree. But the prism contains 2 triangles, while K3,3 is bipartite and has no odd cycles at all. Not isomorphic.
Two graphs without cycles. Both graphs below have degree sequence (3, 2, 2, 1, 1, 1):
H1: 5 ─ 2 ─ 1 ─ 3 ─ 6 H2: 6 ─ 5 ─ 2 ─ 1 ─ 3
│ │
4 4
In H1 the degree-3 vertex (1) has neighbours of degrees 2, 2, 1. In H2 the degree-3 vertex (1) has neighbours of degrees 2, 1, 1. An isomorphism must map the unique degree-3 vertex to the unique degree-3 vertex and its neighbours to its neighbours, preserving degree, which is impossible. Not isomorphic.
C6 and two disjoint triangles. Both are 2-regular on 6 vertices, but one is connected and the other is not.
A strategy for exam questions
Compare |V|, |E| and degree sequences. Any difference → not isomorphic.
Compare finer invariants: triangles, bipartiteness, connectivity, neighbour degrees.
If everything matches, try to build a bijection: match vertices with unique degrees first, then extend along edges.
Verify the bijection on every edge.
Counting Graphs
Labelled graphs. On a fixed vertex set {1, …, n} there are C(n, 2) possible edges, each present or absent independently, so there are 2C(n,2) simple graphs. For n = 4 that is 2⁶ = 64; for n = 5 it is 2¹⁰ = 1024. Those with exactly k edges number C(C(n, 2), k).
Unlabelled graphs (up to isomorphism) are much harder to count, and there is no simple formula. The counts for small n, confirmed by listing every graph:
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
Non-isomorphic simple graphs | 1 | 2 | 4 | 11 | 34 | 156 | 1044 |
For n = 4, the 11 graphs split by number of edges as 1, 1, 2, 3, 2, 1, 1 for 0, 1, …, 6 edges. (The symmetry of that list is no accident: complementing turns a k-edge graph into a (6 − k)-edge graph.)
Self-complementary graphs
A graph is self-complementary if G ≅ Ḡ. Then G and Ḡ have the same number of edges, which must be half of C(n, 2), i.e. n(n − 1)/4. So n(n − 1) must be divisible by 4, which means n ≡ 0 or 1 (mod 4). Examples: the path P4 (complement of a–b–c–d is b–d–a–c, again a path) and the cycle C5 (its complement is the "pentagram", another 5-cycle). On 5 vertices there are exactly two self-complementary graphs: C5 and the "bull" (a triangle with two pendant edges at different corners).
How Hard Is Isomorphism Testing?
The obvious algorithm tries all n! bijections, which is hopeless beyond tiny graphs. Graph isomorphism is one of the few natural problems in NP that is neither known to be solvable in polynomial time nor known to be NP-complete. In 2015 László Babai announced an algorithm running in quasi-polynomial time, exp((log n)O(1)), a major theoretical result. In practice, tools based on clever refinement of invariants (such as nauty) handle very large graphs quickly. Isomorphism testing is used in chemistry (is this molecule already in the database?), circuit verification and pattern matching.
Representations and Isomorphism in Python
from itertools import permutations
def adj_matrix(n, edges):
A = [[0] * n for _ in range(n)]
for u, v in edges:
A[u][v] = A[v][u] = 1
return A
def mat_mul(X, Y):
n = len(X)
return [[sum(X[i][k] * Y[k][j] for k in range(n)) for j in range(n)]
for i in range(n)]
# Vertices a, b, c, d, e are numbered 0..4
names = "abcde"
edges = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (2, 4)]
A = adj_matrix(5, edges)
A2 = mat_mul(A, A)
A3 = mat_mul(A2, A)
print("walks of length 2 from a to c :", A2[0][2])
print("closed walks of length 3 at a :", A3[0][0])
print("triangles = trace(A^3) / 6 :", sum(A3[i][i] for i in range(5)) // 6)
def isomorphism(n, e1, e2):
"""Try every bijection; return one that preserves edges, or None."""
if len(e1) != len(e2):
return None
E2 = {frozenset(e) for e in e2}
for p in permutations(range(n)):
if all(frozenset((p[u], p[v])) in E2 for u, v in e1):
return p
return None
G1 = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)] # 4-cycle + chord 0-2
G2 = [(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)] # 4-cycle + chord 1-3
print("G1 -> G2 mapping :", isomorphism(4, G1, G2))
prism = [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (0, 3), (1, 4), (2, 5)]
k33 = [(i, j) for i in range(3) for j in range(3, 6)]
print("prism isomorphic to K3,3? :", isomorphism(6, prism, k33) is not None)
Output:
walks of length 2 from a to c : 2
closed walks of length 3 at a : 4
triangles = trace(A^3) / 6 : 2
G1 -> G2 mapping : (1, 0, 3, 2)
prism isomorphic to K3,3? : False
The mapping (1, 0, 3, 2) means 0 → 1, 1 → 0, 2 → 3, 3 → 2: the chord 0–2 of G1 goes to the chord 1–3 of G2. Because both edge lists have the same length and f is a bijection, checking that every edge maps to an edge is enough. The brute-force search is fine for 6 vertices (720 permutations) but grows as n!.
Common Mistakes
Concluding "isomorphic" from equal degree sequences. Invariants can only disprove isomorphism.
Checking only edges when edge counts differ. If |E1| ≠ |E2|, stop: not isomorphic. When they are equal and f is a bijection, edges → edges is enough.
Forgetting that the matrix depends on vertex order. Two different adjacency matrices can describe isomorphic graphs.
Using an adjacency matrix for a huge sparse graph. Θ(n²) memory and O(n²) traversal time.
Confusing labelled and unlabelled counts. 2C(n,2) counts labelled graphs; the number up to isomorphism is far smaller.
Interview and GATE-Style Questions
Q1. How many simple graphs can be formed on 5 labelled vertices? How many of them have exactly 3 edges?
2C(5,2) = 2¹⁰ = 1024. With exactly 3 edges: C(10, 3) = 120.
Q2. A is the adjacency matrix of a simple graph and trace(A³) = 30. How many triangles does the graph have?
30/6 = 5.
Q3. How many non-isomorphic simple graphs have 4 vertices and 3 edges? Name them.
3: the triangle plus an isolated vertex, the path P4, and the star K1,3.
Q4. How many edges does a self-complementary graph on 8 vertices have?
Half of C(8, 2) = 28, so 14.
Q5. Your graph has 10⁶ vertices and 5 × 10⁶ edges, and you need to run BFS. Which representation should you use and why?
An adjacency list. It needs Θ(n + m) ≈ 6 × 10⁶ entries (about 10⁷ list entries, since each undirected edge is stored twice) and BFS runs in O(n + m). An adjacency matrix would need 10¹² cells, far too much memory, and BFS on it would take O(n²) time.
Q6. Are C5 and its complement isomorphic? Are K3,3 and its complement isomorphic?
C5: yes (its complement is another 5-cycle). K3,3: no. It has 9 edges, so its complement has 15 − 9 = 6 edges (the complement is two disjoint triangles), and the edge counts differ.
Summary
Adjacency matrix: n × n, symmetric for undirected graphs, Θ(n²) space, O(1) edge test. (Ak)ij counts walks of length k; trace(A³)/6 counts triangles.
Incidence matrix: n × m, two 1s per column. Adjacency list: Θ(n + m) space, the default for sparse graphs and traversals. Edge list: good for sorting edges.
Isomorphism = an adjacency-preserving bijection. Prove it by exhibiting the bijection and checking all edges; disprove it with a differing invariant.
There are 2C(n,2) labelled graphs on n vertices; up to isomorphism, 11 on 4 vertices and 34 on 5.
Self-complementary graphs exist only when n ≡ 0 or 1 (mod 4).
Now that we can store graphs and tell them apart, the next chapter, Euler & Hamiltonian Paths, asks one of the oldest questions in graph theory: can you travel through a graph using every edge, or visiting every vertex, exactly once?