---
tag: 00CT0PTH74
kind: definition
name: Graph isomorphism
msc: [05C60]
defines: 0F7QKGJS6B
uses: [0JD5C82QMB]
sources:
  - url: https://en.wikipedia.org/wiki/Graph_isomorphism
    locator: lead section
---

## Definition

Let $G$ and $H$ be [[graphs|0JD5C82QMB]] with vertex sets $V(G)$ and $V(H)$.
A graph isomorphism from $G$ to $H$ is a bijection $f : V(G) \to V(H)$ such that, for all $u, v \in V(G)$,
$$u \sim v \text{ in } G \iff f(u) \sim f(v) \text{ in } H.$$
The graphs $G$ and $H$ are isomorphic, written $G \cong H$, if there is an isomorphism between them.

## Remarks

Isomorphic graphs have the same number of vertices and edges and the same degrees. They differ only in the names of their vertices.
An isomorphism from $G$ to itself is an automorphism of $G$.
The path $P_4$ is isomorphic to its own [[complement|0RNMP6VCR2]].

## Explanations

### L1 human

Two graphs are isomorphic when one is a relabelling of the other.
Two drawings can look very different and still show isomorphic graphs.