reguläre Graphen Knoten Beweis

Question

Aufgabe:

Zeigen Sie, dass es für jedes gerade n ≥ 4 aus den natürlichen Zahlen immer einen 3-regulären Graphen G = (V, E) mit |V | = n Knoten gibt.

Problem/Ansatz:

Ich habe leider keinen Ansatz wie die Frage gelöst wird.. für Hilfe wäre ich dankbar

Answer 1

Hallo,

gehe induktiv vor. Sei also G ein Graph mit n Knoten, 3-regulär. Wähle 3 Knoten x,y,z aus mit x-y, x-z (soll heißen xy ist eine Kante und xz ist eine Kante.

Konstruiere einen neuen Graphen G' mit 2 neuen Knoten p,q und

- lösche die Kanten xy und xz, dadurch verliert x 2 Grade und y,z jeweils einen.

- verbinde: p-x,p-z,p-q

- verbinde q-x,q-y, (q-p)

Damit habe p und q jeweils 3 Nachbarn, x hat 2 neue Nachbarn, und y und z jeweils einen.

Gruß