Secara intuitif, graf-graf disebut isomorfik jika pada dasarnya sama, atau lebih tepatnya, jika keduanya sama kecuali nama simpul-simpulnya. Untuk merumuskan konsep penggantian nama simpul secara tepat, kita memberikan definisi berikut: