Valenzsequenz eines Graphen

Question

Liebe Community,

ich komme bei der folgenden Aufgabe leider nicht weiter:

Sei nϵN, n>=1. Zeigen oder widerlegen Sie:

a) (n, n-1, n-2, n-3, n-4, ..., 5, 4, 3, 2, 1) ist die Valenzsequenz eines Graphen.

b) (n, n, n-1, n-1, n-2, n-2, n-3, n-3, n-4, n-4, ..., 5, 5, 4, 4, 3, 3, 2, 2, 1, 1) ist die Valenzsequenz eines Graphen.

Hinweis: Wir kennen keine mit endlichem Aufwand aufschreibbare Lösung von (b*) mit dem Verfahren von Havel und Hakimi. Eine Lösung mit Erdös-Gallai wird aufwendig. Die kürzeste Lösung ist eine ad-hoc-Konstruktion.

Bedeutet der Hinweis ebenfalls, dass ich die Lösung zu a) mit dem Verfahren von Havel und Hakimi lösen kann?

Vielen Dank vorab für eure Ansätze zu der Aufgabe!

Answer 1

Also a) ist nicht möglich, da der Graph nur \( n \) Knoten hat, also insbesondere kein Knoten einen Grad grösser als \(n - 1 \) haben kann.

b) Erstmal konstruierst du zwei identische Graphen, nummeriert durch ihre Grade (absteigend sortiert, so wie in der Valenzliste): Dann verbindest du den ersten mit allen anderen, den zweiten mit allen die kleineren Grad als er haben sollen, usw. Als letztes verbindest du noch die Knoten deren Grad noch nicht erschöpft ist mit jenem aus dem identischen Grad, ungefähr so wie im Bild:

Comments

Vielen lieben Dank für die Erklärungen! Das hilft mir sehr weiter :)