Siden grafen er enkel har den ingen løkker eller parallelle kanter. Noden $B$ har grad $2$, så $B$ må være nabo med de to andre naboene. Vi har også at $A$ har grad 1, så $A$ er kun nabo med $B$ og ikke nabo med $C$. $C$ er altså kun nabo med $B$, og må dermed ha grad $1$.
Håndhilselemmaet
Gi tilbakemelding på denne videoen!
Test deg selv
Hvis en enkel graf har noder $A, B, C$ og noden $A$ har grad $1$ og noden $B$ har grad $2$, hvilken grad har node $C$?
Test deg selv
Hvis 4 av 5 noder i en graf har partall grad, har den siste noden partall eller oddetall grad?
Vi vet at summen av gradene til nodene skal bli et partall, og at et partall antall av nodene skal ha odde grad. Hvis den siste noden har oddetall grad vil summen av gradene bli et oddetall, og det vil være et oddetall noder med odde grad. Den siste noden må altså ha partall grad.
Test deg selv
Hvilke av disse listene er mulige lister for gradene på nodene i en graf?
Det kan ikke være et odde antall noder med oddetall grad, så vi kan ikke ha grafer der nodene har grader 3, 3, 3 og 2, eller der nodene har grader 1, 1 og 1. Vi ser at summen av gradene i disse listene heller ikke blir et partall.
Oppgave
Hvilke av disse beskrivelsene gir lovlige, enkle grafer?
Dette gir ikke en lovlig enkel graf siden det ikke er mulig å ha $4$ kanter i en enkel graf med $3$ noder. Det er fordi det maksimale antall kanter en enkel graf med $3$ noder kan ha er $3$; da er alle noder naboer med hverandre. Det går det ikke an å legge til flere kanter uten at vi får løkker eller parallelle kanter, og da er ikke grafen enkel lenger.
Her er det odde antall noder med odde grad, og det bryter med håndhilselemmaet. I tillegg er summen av gradene $7$, og det er ikke mulig at summen av gradene i en graf er et oddetall.
Summen av grader kan ikke være et oddetall.
Dette gir en lovlig enkel graf. Dette er den komplette grafen med $4$ noder ($K_4$).