Théorème des « degrés »

Démonstration

1. Chaque arête du graphe relie exactement 2 sommets, une arête augmente donc de 2 la somme des degrés des sommets (1 pour chaque sommet).
2. Il est clair que, d’après ce qui précède, la somme des degrés est paire.
3. La somme des degrés d’un graphe peut être décomposée en deux sommes :

Chaque terme de la somme  est un entier pair, cette somme est donc paire.

La somme  est nécessairement paire car sinon :  serait impaire (pair + impair = impair ) ce qui est impossible d’après (2).

Un exemple

Est-il possible de dessiner, dans le plan, 9 segments de telle manière que chacun en coupe exactement 3 autres ?

En représentant chaque segment par un sommet d’un graphe et en reliant deux sommets par une arête lorsque les deux segments se coupent, le problème se ramène à la recherche d’un graphe à 9 sommets ou tous les sommets sont d’ordre 3…

Or le nombre de sommets de degrés impairs est nécessairement pair, 9 étant impair, le problème n’a pas de solutions….

En modifiant l’énoncé :

Est-il possible de dessiner, dans le plan, 8 segments de telle manière que chacun en coupe exactement 3 autres ?

Il n’y a plus de contradiction avec le théorème précédent mais il n’est pas sûr que le problème admette une solution…

Quelques tâtonnements permettent cependant de répondre positivement à la question posée