STEP-BY-STEP LESSON · §10.3
Isomorphisms of Graphs
Check graph structure independently of the drawing.
Before you begin
Bijection
A bijection pairs every source object with exactly one target, reaches every target and never sends different source objects to the same target. Graph isomorphism additionally preserves the edge structure.
Adjacency
Two vertices are adjacent if an edge joins them directly. Being reachable by several edges is a different condition. For an undirected graph, reversing an edge’s endpoint names does not create a new edge.
Symbols
- f:V→W
- a bijection between vertex sets
Definitions and notation for this topic
Loops and parallel edges
A loop has the same endpoint twice. Parallel edges are distinct edges with the same endpoints. For an undirected multigraph, retain each edge’s identity and endpoint pair.
A simple undirected graph excludes both loops and parallel edges. The degree convention does not by itself specify how a matrix should record loops; state the matrix convention explicitly.
Separate glossary example
e₁=AB and e₂=AB are two edges, not one duplicated set entry. A loop e₃=AA contributes two to deg(A).
Graph isomorphism
An isomorphism relabels a graph while preserving its incidence structure. For the multigraphs here it consists of a vertex bijection f and an edge bijection g preserving both endpoints of every edge.
Matching vertex counts or degree lists is necessary but not sufficient in general. Distinct parallel edges must have distinct images even when their endpoint pairs coincide.
Separate glossary example
If G has parallel edges e₁,e₂ between A,B and H has h₁,h₂ between x,y, use f(A)=x, f(B)=y and either pairing of the two edge names.
Permutation matrix and relabelling
M_H=PᵀM_GP
For a vertex bijection f from G to H, put P_uv=1 when f(u)=v and 0 otherwise, with rows in G order and columns in H order. For the same adjacency convention, M_H=PᵀM_GP expresses preserved adjacency.
Pᵀ swaps P’s row and column indices. Right multiplication reorders columns and left multiplication by Pᵀ reorders rows. Reversing the convention for P changes the displayed identity; the matrix does not name an edge bijection.
Separate glossary example
If G order is (1,2,3), H order is (p,q,r), and f(1)=r,f(2)=p,f(3)=q, then P=[[0,0,1],[1,0,0],[0,1,0]].
Step by step
Step 1 / 6
Ignore drawing positions
This guide considers finite simple undirected graphs: no loops or parallel edges. An isomorphism renames vertices while preserving adjacency. Stretching or rotating a drawing does not change the structure.
Visual appearance is not the mathematical criterion.
Worked example
V(G)={A,B,C}, with edges AB,BC. V(H)={x,y,z}, with edges xy,xz. Are these graphs isomorphic?
- B has degree 2; x has degree 2 in H. Set f(B)=x.
- Set f(A)=y, f(C)=z. Edges become yx,xz; missing AC becomes missing yz.
- This bijection preserves adjacency in both directions, so it is an isomorphism.
Optional self-check
Two graphs have the same degree sequence. One is connected and the other disconnected. Can trying a cleverer renaming make them isomorphic?
Show answer
No. A path between vertices maps to a path between their images, so a bijection preserving adjacency also preserves connectedness.