Isomorfisma Graf

Dalam geometri, dua gambar disebut kongruen jika keduanya mempunyai sifat-sifat geometri yang sama. Dengan cara yang sama, dua graf disebut isomorfis jika keduanya menunjukkan "bentuk" yang sama. Kedua graf hanya berbeda dalam hal pemberian label titik dan garisnya saja. Secara matematis, isomorfisma 2 graf didefinisikan dalam contoh berikut :

Misalkan G adalah suatu graf dengan himpunan titik V(G) dan himpunan garis E(G). G' adalah graf dengan himpunan titik V(G') dan himpunan garis E(G').

G isomorfis dengan G' bila dan hanya bila ada korespondensi satu-satu

•V(G) → V(G') dan

•E(G) → E(G')

Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul simpul keduanya dan antara sisi-sisi keduaya 

Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda.  Ini benar karena sebuah graf dapat digambarkan dalam banyak cara. Contoh :

Hingga saat ini belum ada teori yang dapat dipakai untuk menentukan apakah dua graf G dan G' isomorfis. Akan tetapi, jika G dan G' isomorfis, maka terdapat beberapa hal yang pasti dipenuhi:

• —jumlah titik G = jumlah titik G'
• —jumlah garis G = jumlah garis G'
• —jumlah garis dengan derajat tertentu dalam G dan G' sama.

Masalahnya, implikasi tersebut tidak berlaku 2 arah. Ada 2 graf yang memenuhi ketiga syarat tersebut, tetapi keduanya tidak isomorfis. Sebagai contoh adalah graf G dan G' pada Gambar ini :

                            G                                     G'
Dalam G, satu-satunya titik yang berderajat 3 adalah titik x. Titik x dihubungkan dengan 2 titik lain yang berderajat 1 (titik y dan z).

Sebaliknya, dalam G', satu-satunya titik yang berderajat 3 adalah v. Satu-satunya titik berderajat 1 yang dihubungkan dengan v hanyalah titik w, sehingga G tidak mungkin isomorfis dengan G'.