Paar von Abbildungen zwischen zwei Graphen der folgenden Art.

Ein Graphenhomomorphismus von einem GraphenG in einen Graphen H besteht aus zwei Abbildungen f : E(G) → E(H) sowie F : K(G) → K(H), die für alle k = xy ∈ K(G) die folgende Bedingung erfüllen: \begin{eqnarray}k=xy\Rightarrow F(k)=f(x)f(y).\end{eqnarray}

Sind die Abbildungen f und F bijektiv, so nennt man die Graphen G und H isomorph, in Zeichen G ≅ H.

Isomorphe Graphen werden als im wesentlichen gleich angesehen. Trotz aller Anstrengungen hat man bisher keinen polynomialen Algorithmus gefunden, um festzustellen, ob zwei beliebig gegebene Graphen isomorph sind. Dieses sogenannte Graphenisomorphieproblem ist eines der bekanntesten Probleme, dessen Komplexitätsstatus noch immer ungeklärt ist.

Ein Graph G wird selbstkomplementär genannt, wenn \(G\cong \bar{G}\) gilt, wobei \(\bar{G}\) der Komplementärgraph von G ist. Der Weg der Länge 3 oder der Kreis der Länge 5 sind Beispiele für selbstkomplementäre Graphen. Da der vollständige Graph K_n aus n(n − 1)/2 Kanten besteht, gibt es in einem selbstkomplementären Graphen mit n Ecken genau n(n − 1)/4 Kanten. Daher gilt für die Ordnung n eines selbstkomplementären Graphen notwendig n = 4p oder n = 4p + 1. H. Sachs (1962) und G. Ringel (1963) zeigten, daß es für jede natürliche Zahl p tatsächlich selbstkomplementäre Graphen der Ordnung 4p und 4p + 1 gibt.

Graphenhomomorphismen und -isomorphismen lassen sich entsprechend auch für gerichtete Graphen erklären.