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.
This article has been written by Robin Pourtaud ([email protected]) and published on December 26, 2022.
The content of this article is licensed under CC BY
NC 4.0 : You can freely share and adapt the content for non-commercial purposes as long as you give
appropriate credit and provide a link to the license. In my case, the link to the original article is enough.
Confidentiality if relevant: https://devmath.fr/page/confidentialite/
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.