Izomorfismus grafů

Nechť a jsou dva grafy

Funkce je izomorfismus grafů a , pokud:

• je bijekce
• a pro každou dvojici vrcholů z platí
  právě tehdy, když
• právě tehdy, když

Tedy grafy jsou izomorfní, pokud mají hranami spojené stejné vrcholy (i když jinak pojmenované)

• Hrana přilehne na hranu
• Nehrana přilehne na nehranu

Izomorfismus značíme