Key takeaways
- Graphs G and H are isomorphic when there is a bijection between their vertex sets that sends edges to edges and non-edges to non-edges.
- To prove isomorphism, give the bijection explicitly and check every edge.
- To disprove it, find an invariant that differs: number of vertices or edges, degree sequence, connectedness, cycle lengths or bipartiteness.
- Matching invariants do not prove isomorphism: a 6-cycle and two separate triangles share a degree sequence but are not isomorphic.
- No polynomial-time algorithm is known for testing isomorphism in general, though small cases are quick by hand.
The same graph can be drawn in endlessly many ways. Move the dots, bend the edges, rename the vertices, and you still have the same network of connections. Graph isomorphism makes "the same graph" precise, and deciding whether two drawings show the same graph is a skill you can learn as a checklist.
A bijection that preserves edges
MathWorld's definition: a graph isomorphism from a simple graph G to a simple graph H is a bijection f from the vertices of G to the vertices of H such that u and v are adjacent in G if and only if f(u) and f(v) are adjacent in H. If such an f exists, G and H are isomorphic, written G ≅ H.
The "if and only if" matters: edges must go to edges, and non-edges must go to non-edges. OpenStax's Contemporary Mathematics puts the idea informally: as long as two graphs indicate the same pattern of connections, they are considered isomorphic, whatever the labels.
The bijection is a one-to-one and onto function on the vertices, and "is isomorphic to" is an equivalence relation on graphs, which is why it makes sense to talk about "the same graph".
Proving two graphs are isomorphic
Give the bijection and check the edges.
Example. G has vertices a, b, c, d and edges ab, bc, cd, da: a square. H has vertices 1, 2, 3, 4 and edges 13, 32, 24, 41, drawn as a bow-tie shape with crossing edges. They look different. Try
f(a) = 1, f(b) = 3, f(c) = 2, f(d) = 4.
| Edge in G | Image in H | Edge in H? |
|---|---|---|
| ab | 13 | Yes |
| bc | 32 | Yes |
| cd | 24 | Yes |
| da | 41 | Yes |
All four edges map to edges, and both graphs have exactly four edges, so the four images are all of H's edges. Non-edges then map to non-edges automatically. So G ≅ H: both are the 4-cycle C₄.
How to find the bijection. Match vertices with the same degree. Then match neighbours to neighbours: if a goes to 1, a's neighbours must go to 1's neighbours. Special vertices, such as the only one of degree 4 or the one lying on every triangle, are good anchors.
Proving two graphs are not isomorphic
An invariant is a property that isomorphic graphs always share. If the graphs differ on any invariant, they are not isomorphic. The standard checklist, roughly in order of how quick it is to check:
- Number of vertices.
- Number of edges.
- Degree sequence (the list of degrees, sorted).
- Connectedness and number of components.
- Number of triangles, or of cycles of each length.
- Whether the graph is bipartite.
- Degrees of neighbours: for example, whether the degree-3 vertices are adjacent to each other.
- Whether the graph is planar.
OpenStax recommends exactly this approach: check first for obvious ways the graphs might differ before spending time trying to build an isomorphism.
Example. C₆, a hexagon, and two separate triangles. Both have 6 vertices, 6 edges and every degree 2, so the first three invariants agree. But C₆ is connected and the triangles are not, so they are not isomorphic. Equally, the triangles contain 3-cycles and the hexagon does not.
Example. Two graphs on 5 vertices with degree sequences (3, 3, 2, 2, 2) and (3, 2, 2, 2, 1) cannot be isomorphic: their degree sequences differ.
The trap: matching invariants prove nothing
Every invariant is a necessary condition for isomorphism, never a sufficient one. The C₆ example shows two graphs with the same counts and degree sequence that are still different. No finite list of the simple invariants above is known to settle every case, so when all your invariants match, the only way to prove isomorphism is to find the bijection.
How hard is it?
For two graphs with n vertices there are n! possible bijections. Checking them all is hopeless beyond small n: 10 vertices already give 3,628,800 candidates. MathWorld notes that no polynomial-time algorithm is known for graph isomorphism testing, although the problem has also not been shown to be NP-complete, and the special complexity class "graph isomorphism complete" is sometimes used for problems equivalent to it. By hand, invariants and anchoring cut the search down enormously.
Counting graphs up to isomorphism
Isomorphism lets you count "different" graphs meaningfully. There are 2³ = 8 labelled simple graphs on 3 vertices, since each of the three possible edges is present or absent, but only 4 up to isomorphism: no edges, one edge, a path of two edges, and a triangle. The number of edges alone distinguishes them here, but that stops working for larger graphs, which is part of what makes the counting hard.
Pairs of graphs to compare
- Are the graphs with edge sets {12, 23, 34, 45} and {13, 35, 52, 24} on vertices 1 to 5 isomorphic? (Both are paths on 5 vertices: yes. Map the path 1-2-3-4-5 to 4-2-5-3-1.)
- A graph has degree sequence (2, 2, 2, 2). Must it be C₄? (Yes, on 4 vertices: a 2-regular graph is a union of cycles, and 4 vertices allow only one 4-cycle.)
- Find two non-isomorphic graphs with degree sequence (3, 3, 3, 3, 3, 3). (K₃,₃, which has no triangles, and the triangular prism, which has two.)
Isomorphism builds on graph theory basics, and computer checks often compare adjacency matrices, since two graphs are isomorphic exactly when some reordering of one's rows and columns gives the other. Levin's open textbook covers isomorphism in its graph theory definitions. Graphs are the last unit of Discrete Math: Study & Quiz, listed with our other education apps; the discrete math hub has the rest of the series.
Good to know
Frequently asked questions
What is a graph isomorphism?
How do you prove two graphs are isomorphic?
How do you prove two graphs are not isomorphic?
Is having the same degree sequence enough for isomorphism?
Sources
- Graph Isomorphism (opens in a new tab)Wolfram MathWorld — accessed
- 12.3 Comparing Graphs (Contemporary Mathematics) (opens in a new tab)OpenStax — accessed
- Graph Theory: Definitions (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.