Dacă n este un număr natural impar mai mare decât 2, atunci un graf neorientat cu n noduri, în care fiecare nod este adiacent cu exact n-1 noduri, este întotdeauna:
n
2
n-1
arbore
graf eulerian
graf neconex
graf aciclic (graf care nu conţine niciun ciclu)