Det finnes ikke noe selv-komplementær graf med $3$ noder. Hvis $G$ er en enkel graf med $3$ noder, kan $G$ maksimalt ha $3$ kanter, for da er alle nodene naboer. Dersom $G$ har $1$ kant, vil $\overline{G}$ ha $2$. For at $G$ og $\overline{G}$ skal ha samme antall kanter, må $G$ ha halvparten antall kanter av det maksimale, nemlig $1.5$, men det er umulig å ha halve kanter. Altså må maksimalt antall kanter i en graf være et partall for at det kan finnes en selv-komplementær graf.
Avgjøre om to grafer er isomorfe
Oppgave
Hva skal til for at to endelige grafer $G$ og $H$ er isomorfe? Det kan være flere riktige svar.
Hvis dette stemmer, så er $G$ og $H$ isomorfe. Det er fordi dersom $G$ og $H$ har like mange noder, og det finnes en injektiv funksjon fra nodene til $G$ til nodene til $H$, er denne funksjonen også bijektiv. Hvis definisjonsmengden og verdimengden har samme antall elementer, er en injektiv funksjon alltid også surjektiv, og dermed er den bijektiv.
Dette er definisjonen av isomorfi, så hvis dette stemmer er $G$ og $H$ isomorfe.
$G$ og $H$ må ikke nødvendigvis være isomorfe hvis dette stemmer. Det er fordi det kan finnes en surjektiv funksjon fra nodene til $G$ til nodene til $H$, selv om $G$ har flere noder enn $H$. Hvis vi i tillegg hadde fått vite at $G$ og $H$ har samme antall noder, hadde dette også betydd at $G$ og $H$ er isomorfe.
Oppgave
En graf $G$ er selv-komplementær dersom komplementet til $G$ er isomorf med $G$ selv. Finnes det en selv-komplementær graf med tre noder?
Oppgave
En graf $G$ er selv-komplementær dersom komplementet til $G$ er isomorf med $G$ selv. Hva er det minste antall noder en graf kan ha for at den er selv-komplementær? Her teller vi ikke med grafer med én node.