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
Student hbo - maandag 18 oktober 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.