I $\overline{G}$ skal to noder være naboer hvis og bare hvis de ikke er naboer i $G$. Siden alle par av noder i $G$ er naboer, er ingen noder naboer i $\overline{G}$, og grafen har null kanter.
Kapitteltest – Kapittel 21
Oppgave
La $G$ være en komplett graf med $n$ noder. Hvor mange kanter har $\overline{G}$?
Oppgave
Anta at grafen $G$ har $6$ noder, og summen av gradene til disse nodene er $22$. Hvor mange kanter har $\overline{G}$?
Siden summen av gradene er $22$, har $G$ $\frac{22}{2} = 11$ kanter. Den komplette grafen med $6$ noder har $\binom{6}{2} = 15$ kanter. Siden $\overline{G}$ inneholder de kantene som ikke er i $G$, får vi da at $\overline{G}$ har $15-11 = 4$ kanter.
Oppgave
Hvilke av disse listene er mulige lister for gradene på nodene i en enkel graf?
Det er ikke mulig at en graf med tre noder har noder med grad $3$. Hver node kan bare ha en kant til to andre noder, altså er den høyeste graden en node kan ha i en graf med tre noder kun $2$.
Dette gir en lovlig, enkel graf. Dette er en graf med $5$ noder, hvor alle nodene har grad $4$, altså hvor det finnes en kant mellom alle noder. Det er den altså den komplette grafen med $5$ noder ($K_5$).
Dette gir en lovlig, enkel graf. Det er partall antall noder som har odde grad.
Dette er ikke mulig, for her er det odde antall noder med odde grad.
Oppgave
La grafen $G$ ha nodene $X =\set{1,2,3,4}$ og kantene $\set{\set{1,2}, \set{1,4}, \set{2,3}, \set{3,4}}$. La grafen $H$ ha nodene $Y = \set{A, B, C, D}$ og kantene $\set{\set{A,C}, \set{A,D}, \set{B,D}, \set{B,C}}$.
Er de to grafene isomorfe? Hvis ja, hvilke(n) av bijeksjonene fra $X$ til $Y$ beviser at de er isomorfe?
Tips: tegn grafene og bijeksjonene!
Oppgave
La $G$ være en enkel graf med $n$ noder, der $n$ er et naturlig tall større eller lik $2$. La $G$ ha én mindre kant enn den komplette grafen med $n$ noder har. Er $G$ isomorf med alle grafer med like mange noder og like mange kanter?
To av nodene i $G$ vil ha grad $n-2$, mens resten vil ha grad $n-1$. La $H$ være en vilkårlig graf med de gitte egenskapene. Lager vi en bijeksjon fra nodene i $G$ til nodene i $H$, kan vi sende de to nodene i $G$ med grad $n-2$ til de to i $H$ med grad $n-2$, og resten kan vi sende hvor som helst (så lenge det er en bijeksjon). En slik bijeksjon vil oppfylle kravet slik at $G$ og $H$ er isomorfe.