Graph isomorphism

Definition

Let $G$ and $H$ be graphs 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.

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.