Supposons qu'un graphe simple a 18 arêtes, 4 sommets de degré 3 et tous les autres de degré 4. Combien de sommets le graphe a-t-il ?

Un graphe simple n'a pas d'arêtes connectées d'un nœud à lui-même, donc le total des degrés de tous les sommets impliqués sera 2*18 = 36. Le total des degrés des sommets du degré 3 est de 12, donc le total des degrés du degré 4 sommets doivent être 36 - 12 = 24. Il doit y avoir 24/4 = 6 sommets de degré 4, soit un total de 10 sommets dans le graphe.

Vous pouvez construire un tel graphique comme suit. Identifiez les sommets avec les numéros 1 à 10. Faites les connexions suivantes :
(1-2-3-4-5-6-7-8-9-10-1)
(2-4)
(7-9)
(1- 5-8-1)
(3-6-10-3) Les
sommets 2, 4, 7, 9 auront le degré 3. Les autres auront le degré 4. (Il existe de nombreuses autres possibilités.)