Théorème

Soit $G = (V, E)$ un graphe simple (sans boucle), $V$ l’ensemble des sommets et $E$ l’ensemble des arêtes. On appelle degré d’un sommet $v$ le nombre d’arêtes adjacentes à $v$.

G possède au moins deux sommets de degré égal.

Démonstration

Nous allons démontrer le théorème par contradiction.

Soit $v \in V$, on note $n = |V|$ le nombre de sommets.

D’après le théorème du degré d’un sommet, on a $0 \leq deg(v) \leq n-1$.

Supposons par contradiction que tous les sommets de G ont des degrés différents.

L’ensemble des degrés $D$ des sommets est donc :

$$D = \{0,1,2, \ldots, n-1\}$$

Cependant, ce graphe ne peut pas avoir un sommet de degré $n-1$ et un de degré $0$.

En effet, supposons qu’un sommet $u$ existe tel que $deg(u) = n-1$. Alors $u$ doit être connecté à $n-1$ autres sommets.

Prenons pour exemple un graphe de 2 sommets. On a $D = \{0,1\}$, or, si $v_1$ a une arête, $v_1$ est forcément connecté à $v_2$, or $v_2$ doit ne pas avoir d’arête pour avoir un degré différent de $v_1$. Contradiction.

Nous avons donc soit :

• $$D = \{0,1,2, \ldots, n-2\}$$
• $$D = \{1,2, \ldots, n-1\}$$

Tel que $|D| = n-1$.

Par the principe des tiroirs de Dirichlet, nous avons |V| = n et |D| = n-1, donc il existe au moins deux sommets de degré égal.