Homomorfismo e Isomorfismo
Definição: Homomorfismo
Sejam $G=(V,E)$ e $G'=(V',E')$ dois grafos. Um mapa $\varphi : V \to V'$ é um homomorfismo de $G$ para $G'$ se ele preserva a adjacência de vértices, isto é, se $\{\varphi (x),\varphi (y)\} \in E'$ sempre que $\{x,y\} \in E$. Em particular, para cada $x'$ na imagem de $\varphi$ sua imagem inversa $\varphi ^{-1} (x')$ é um conjunto independente de vértices em $G$.
Definição: Isomorfismo
Se $\varphi$ é bijetivo e seu inverso $\varphi ^{-1}$ também é um homomorfismo (de modo que $xy \in E \Leftrightarrow \varphi (x) \varphi (y) \in E'$ para todo $x,y \in V$), chamamos $\varphi$ de isomorfismo, dizemos que $G$ e $G'$ são isomórficos e escrevemos $G \simeq G'$. Um isomorfismo de $G$ para si mesmo é um automorfismo de $G$.