Đẳng cấu đồ thị
Hai đồ thị G1 và G2 được gọi là đẳng cấu với nhau, ký hiệu là "G1 ≈ G2", nếu có thể vẽ lại (bằng cách dời đỉnh, dời cạnh...) sao cho hai đồ thị này có hình vẽ y hệt nhau. Dựa trên cơ sở sự hoán vị đỉnh và hoán vị cạnh, người ta phân biệt thành 2 trường hợp là đồ thị có hướng và đồ thị vô hướng.

Hai đồ thị đẳng cấu thì ta có: 
=> Nếu hai đồ thị có ma trận kề (theo một thứ tự đỉnh nào đó) bằng nhau thì chúng đẳng cấu với nhau.
Ta có song ánh:
Để có được song ánh như trên thì:







