Démonstration : 2 sommets de degrés égaux
Dans un graphe simple (non orienté sans boucle), il existe au moins deux sommets de degré égal.
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.