Selbskomplementäre Graphen

G heißt selbstkomplementär, falls G $\cong$ $\overline{G}$.

Der folgende Graph auf 4k Knoten ist selbst-komplementär:

• V = {a, b, c, d}×{1, 2,..., k}
• E enthält:
  • alle Kanten innerhalb {b}×{1, 2,..., k} -- kurz: (b,*)
  • alle Kanten innerhalb (c,*)
  • alle Kanten (a,*) - (b,*) - (c,*) - (d,*)

Beweis: die Isomorphie f : G$\to$$\overline{G}$ ist f : (a, x) $\mapsto$ (c, x),(b, x) $\mapsto$ (a, x),(c, x) $\mapsto$ (d, x),(d, x) $\mapsto$ (b, x).

Aufgabe: konstruiere (mit Beweis) selbstkomplementäre Graphen mit 4k + 1 Knoten!