Geben Sie zwei Graphen an, die nicht Isomorph sind. Knotengrad gegeben

Question

Aufgabe:

Geben Sie zwei Graphen mit je fünf Knoten und fünf Kanten an, die nicht isomorph sind, wobei die Knoten die Grade 1,2,2,2,3 haben.

Problem/Ansatz:

Habe hier eine Lösung gefunden aus einer Lösungssammlung von Kommilitonen. Ich kann nicht nachvollziehen, warum das nicht isomorph sein soll.
Grundlegend "einfach" zusammengefasst gilt:
- Anzahl Knoten und Kanten muss gleich sein.
- Kontengrade müssen gleich sein.

Das wird doch hier erfüllt, oder nicht?

Kann mir jemand weiterhelfen?

Answer 1

Sei $f: \{a,b,c,d,e\}\to\{a',b',c',d',e'\}$.

Angenommen $f$ ist ein Isomorphismus.

Dann ist $f(a) = a'$, weil $a$ und $a'$ die einzigen Knoten mit Knotengrad 1 sind.

Außerdem ist $f(b) = c'$, weil $b$ der einzige mit $a$ inzidente Knoten ist und $c'$ der einzige mit $f(a)$ inzidente Knoten ist.

$b$ hat Knotengrad 2 und $c'$ hat Knotengrad 3.

Das ist ein Widerspruch zu der Annahme $f$ sei ein Isomorphismus.

- Kontengrade müssen gleich sein.

Knotengrade entsprechender Knoten müssen gleich sein.

Das heißt ist $f(x) = y$, dann ist der Knotengrad von $x$ gleich dem von $y$.

Grundlegend "einfach" zusammengefasst gilt:
- Anzahl Knoten und Kanten muss gleich sein.
- Kontengrade müssen gleich sein.

Das reicht für einen Isomorphisms nicht. Eine bessere Vorstellung von Isomorphismus ist, dass der eine Graph in einen andere Graphen übergeht indem die Knoten umbenannt werden.

Answer 2

Die fehlende Isomorphie kann man z.B daran erkennen, dass V nur einen Kreis mit 4 Knoten hat, aber V' nur einen Kreis mit 3 Knoten.