TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 284

Ein schlichter Graph $G=(V,E)$ 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\cdot n$ gibt!

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von mnemetz

a) Beispielgraph G = 6

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

ANMERKUNG: $\alpha _{0}(G)=6$ heißt 6 Knoten. Die Skizze zeigt allerdings 8 Knoten, kleiner Fehler... Den richtigen Graphen findet man auf Wikipedia bei Kubischer Graph.

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:

$\sum _{v\in V(G)}d(v)=2\cdot |E(G)|$

Nachdem gemäß der Definition des kubischen Graph aus der Angabe jeder Knoten $v$ Knotengrad $d(v)=3$ hat, ist die Summe aller Grad die Anzahl der Knoten $\alpha _{0}(G)$ multipliziert mit $3$ Grad:

$\sum _{v\in V(G)}d(v)=3\cdot \alpha _{0}(G)$

Das kann man sich leicht überlegen, in dem man sich den kubischen Graph von weiter oben vorstellt, die Knoten abzählt (entspricht $\alpha _{0}(G)$) und mit der Anzahl der Grad ($3$) für jeden Knoten multipliziert. Das ergibt dann die Summe über alle Grad.

Die Summe über alle Grad ist immer noch die doppelte Kantenanzahl nach dem Handschlaglemma:

$3\cdot \alpha _{0}(G)=2\cdot |E(G)|$

Somit muss aber $\alpha _{0}(G)$ eine gerade Zahl sein, da das Doppelte der Kantenanzahl auch immer gerade ist, der Faktor $3$ aber ungerade. Womit es keinen kubischen Graph mit ungerader Knotenanzahl $\alpha _{0}(G)$ geben kann.

c) Verallgemeinerung kubischer Graph

Zeigen Sie, daß es zu jedem $n\geq 2$ einen kubischen Graphen mit $\alpha _{0}(G)=2\cdot 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