Gibt es einen Graphen mit der Gradfolge (5,3,3,2,2,2,1)

Question

(5,3,3,2,2,2,1)

Ich kann erkennen das V =  7 ist.

E ist nach der Gradsummenformel = 9

Die Definition des Handshake-Lemmas ist erfüllt, da die Anzahl der ungeraden Knoten gerade ist.

Wie kann ich jetzt erkennen ob es tatsächlich einen Graphen gibt?

Zeichnerisch hab ich es nicht geschafft einen zu zeichnen, doch das ist kein Beweis dafür, dass es keinen gibt.

Die Aussage "E ist eine Teilmenge von V über 2" kann ich nicht ganz richtig deuten?

7 über 2 ist ja 21, doch ist 9 eine Teilmenge von 21? Beide sind durch 3 teilbar, doch hilft mir das weiter?

Answer 1

"V über 2" ist eine Bezeichnung für alle Teilmengen von V mit genau zwei Elementen, also alle möglichen Kanten.

Ein Graph mit der angegebenen Gradsequenz ist:

1-2,1-3,1-4,1-5,1-6
2-3,2-7
3-4
5-6

Comments

jetzt weiß ich zwar das es einen Graphen gibt, aber nicht woher und warum. Was brauche ich um eine ausreichende Aussage zu treffen ob es einen Graphen gibt? Reicht es zu sagen, das die Anzahl der ungeraden Knoten gerade ist und vielleicht das die Anzahl der Kanten <= (V über 2) ist?

Danke schonmal für deine Mühe