K-regulärer Graph mit vorgegebenen Knoten zeichnen

Question

Aufgabe:

Ein \( k \)-regulärer Graph ist ein Graph, in welchem jeder Knoten Grad \( k \) hat.
1. Zeichne einen 3-regulären Graph mit 8 Knoten. Wenn nicht möglich, erkläre Warum.
2. Zeichne einen 3-regulären Graph mit 7 Knoten. Wenn nicht möglich, erkläre weshalb.

Problem/Ansatz:

Kann jemand mir helfen? Danke

Answer 1

1.: Zu den Kanten eines regelmäßigen 8-Ecks füge
die Verbindungskanten gegenüberliegender Knoten (Ecken) hinzu.
Das liefert, da jede Kante zwei Endknoten besitzt,
\(3\cdot 8 / 2=12\) Kanten.

2.: Bei einem 3-regulären Graphen mit 7 Knoten,
hätte man \(3\cdot 7 / 2\) Kanten. Das ist aber keine ganze Zahl.