WisFaq!

Zelf-complementaire graaf

Hey allemaal,

Kan iemand mij helpen iets te bewijzen?

Het gaat over zelf-complementaire grafen, een zelf-complementaire graaf is een graaf G die isomorf is met zijn complement.

Bewijs dat het aantal punten van een zelf-complementaire graaf altijd een 4-voud óf een 4-voud + 1 is.

Ik heb van alles lopen tekenen en gezocht op internet maar ik kan helemaal niks vinden!

Iemand een idee'tje?

Groet,
Bas

Bas
18-10-2010

Antwoord

Laat n het aantal knopen zijn. De takken en die van de complementaire graaf geven samen alle mogelijke takken tussen die n knopen; dat laatste aantal is n(n-1)/2 en dat moet blijkbaar even zijn.

kphart
18-10-2010