Nichtisomorphie zeigen auf Graphen/Bäumen

Question

Hallo liebe Community,

ich fehlt glaube ich leider die nötige Kreativität für die folgende Aufgabe:

Zeigen Sie: Es gibt zwei untereinander nicht isomorphe und zu T nicht isomorphe Graphen G1 und G2 mit der Valenzsequenz (3, 2, 2, 1, 1, 1). Beweisen Sie die paarweise Nichtisomorphie der drei Graphen G1, G2 und T. Hinweis: Einer der beiden Graphen G1 und G2 ist ein Baum.

Meine Gedanken: T ist ja auch ein Baum, aber alle anderen Bäume die ich mit der Valenzsequenz konstruiere, sind isomorph zu T. Ich hätte noch die Idee einen Graphen mit einem Kreis zu zeichnen, der wäre auf jeden Fall nicht isomorph zu T. Aber wie zeige ich am Ende formal die Nicht Isomorphie, wenn die Valenzsequenzen die gleichen sind?

Vielen lieben Dank vorab!

Answer 1

Hallo,

das sind die drei möglichen Graphen (bis auf Isomorphie).

Der rechte Graph ist nicht zusammenhängend, daher nicht isomorph zu einem der anderen.

In diesen Graphen ist jeweils der eine Punkt mit Grad 3 ausgezeichnet / eindeutig. Im linken Graphen hat dieser Punkt 2 Nachbarn mit Grad 2, im mittleren nur einen Nachbar mit Grad 2; daher sind die beiden linken nicht isomorph.

Comments

Vielen lieben Dank für deine Hilfe!