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
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?
Test deg selv
Hvilke av disse listene er mulige lister for gradene på nodene i en graf?
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$).