TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 172

Angabe

Ein schlichter Graph $G=\langle V,E\rangle$ heißt kubisch, wenn jeder Knoten $v\in V$ Knotengrad d(v) = 3 hat.

a) Geben Sie ein Beispiel für einen kubischen Graphen mit $\alpha _{0}(G)=6$ an!

b) Gibt es einen kubischen Graphen mit ungerader Knotenanzahl $\alpha _{0}(G)$?

c) Zeigen Sie, daß es zu jedem $n\geq 2$ einen kubischen Graphen mit $\alpha _{0}{G}=2*n$ gibt!

Lösungsvorschlag von mnemetz

a) Beispielgraph G = 6

Geben Sie ein Beispiel für einen kubischen Graphen mit $\alpha _{0}(G)=6$ an!

b) Kubischer Graph mit ungerader Knotenanzahl

Gibt es einen kubischen Graphen mit ungerader Knotenanzahl $\alpha _{0}(G)$?

Somit können wir in den Aufgabenstellungen einen ungerichten Graphen ohne Mehrfachkanten nur dann zeichnen, wenn das Handschlaglemma gilt: Die Summe über die Grade aller Knoten eines Graphen ist gleich der doppelten Kantenanzahl in dem Graphen.

Da die doppelte Kantenanzahl gerade ist, muss die Summe über die Grade aller Knoten auch gerade sein. In der Summe darf ich beliebig Klammern setzen, also auch einmal um alle geraden Summanden (diese Summe ist auf jeden fall gerade), und dann einmal um alle ungeraden Summanden; damit die zweite Summe gerade ist, muss die anzahl deren Summanden gerade sein. Nun ist aber jeder Summand Grad eines Knotens; diese Knoten haben alle ungeraden Grad; d.h. die Anzahl der Knoten mit ungeradem Grad ist gerade.

Da aber die Anzahk der Knoten mit ungeradem Knotengrad ungerade ist, kann ein solcher kubischer Graph nicht existieren!

c) Verallgemeinerung kubischer Graph

Zeigen Sie, daß es zu jedem $n\geq 2$ einen kubischen Graphen mit $\alpha _{0}{G}=2*n$ gibt!

Der kubische Graph mit z.B. n = 8 schaut von der Anordnung so aus:

   "unterer Teil"          "oberer Teil"
  |-----------------------------------|
  3   2   1                   1   2   3
      |   |-------------------+---|
      |-----------------------|
        
           ^^^^^^^^^^^^^^^^^^^^
             2   1    1   2
           einfügen n mal