Motivation
Wir betrachten die Graphen
G1 = ({ a, b, c, d }, { ab, ac, ad, bc }) und
G2 = ({ 1, 2, 3, 4 }), { 12, 13, 23, 24 }),
wobei die Ecken a, b, c, d des ersten Graphen beliebige paarweise verschiedene Objekte sind.
Die beiden Graphen lassen sich, wenn wir von den Namen ihrer Ecken absehen, jeweils als Dreieck mit einer an einer Ecke des Dreiecks angefügten Kante beschreiben. Sie sind aus graphentheoretischer Sicht strukturgleich. Der visuelle Unterschied, der sich durch die sich kreuzenden Kanten im Diagramm rechts ergibt, betrifft lediglich die Darstellung, nicht die Struktur der Graphen. Die Umbenennung (oder aus der Sicht eines Ecken-Kanten-Diagramms: Verschiebung)
a ↦ 2, b ↦ 1, c ↦ 3, d ↦ 4
der Ecken führt den Graphen G1 in den Graphen G2 über. Diese Umbenennung können wir visualisieren, indem wir die zugeordneten Ecken gleich einfärben:
Ebenso könnten wir die folgende Umbenennung verwenden:
a ↦ 2, b ↦ 3, c ↦ 1, d ↦ 4
Dagegen wäre eine Umbenennung, die die Ecke c der Ecke 2 zuordnet, nicht geeignet, denn die Ecken c und 2 haben unterschiedliche Eigenschaften in den beiden Graphen. Beispielsweise hat die Ecke c in G1 zwei Nachbarn, die Ecke 2 in G2 dagegen drei.
Kurz und anschaulich können wir die Situation so zusammenfassen:
Die Graphen G1 und G2 unterscheiden sich nur durch die Namen ihrer Ecken.
Nachdem die Namen der Ecken im Hinblick auf die Struktur des Graphen keine Rolle spielen, können wir die Graphen auch zeichnen, ohne den Ecken Namen zu geben. Die folgenden Diagramme sind in diesem Sinne gleichwertig und repräsentieren jeweils sowohl G1 als auch G2. Anschaulich können sie durch eine geeignete Verschiebung der Ecken ineinander übergeführt werden.