Un graphe -régulier admet forcément un noeud de degré

Il existe un graphe simple d'ordre et de taille  

Dans un graphe simple, la somme des degrés des noeuds est égale à deux fois le nombre d'arêtes

Un graphe simple d'ordre est de taille inférieure ou égale à

Soit un sommet d'un graphe. Alors

Soit une arête d'un graphe. Alors