Ein Graph wird selbst-komplementär genannt, wenn alle Kanten, die man für ihn nicht verwendet wurden, zusammen denselben Graphen bilden. Selbst-komplementäre Graphen sind gut verstanden: Man weiß, wie viele selbst-komplementäre Graphen es gibt. Und es ist ziemlich einfach zu zeigen, dass ein selbst-komplementärer Graph immer eine Knotenanzahl hat, die bei Division durch 4 immer Rest 0 oder 1 ergibt. Nur etwas schwieriger ist der Beweis, dass es für solche Zahlen immer mindestens einen selbst-komplementären Graphen gibt. Einen graphischen Beweis dafür liefern diese Bilder:
Wer sich diese Bilder genau ansieht, merkt nämlich schnell, wie die Konstruktion ist und dass sie leicht auch auf andere Knotenzahlen erweitert werden kann.
Doch es gibt noch offene Fragen: Zum Beispiel die, ob man alle selbst-komplementären Graphen mit einer gewissen Knotenzahl auch schnell auflisten kann.
Andreas Loos