Considérons un réseau social dans lequel les membres peuvent choisir d’être amis(si $a$ est ami de $b$, alors $b$ est nécessairement ami de $a$). Nous souhaitons montrer qu’il existe au moins deux membres du réseau qui ont le même nombre d’amis, et qu’il existe un nombre pair de membres ayant un nombre impair d’amis.
On définit le graphe simple non orienté $G = (S, A)$ avec : $$S = \{ s \mid s \text{ est un membre du réseau} \}$$ $$A = \{ \{ i, j \} \subseteq S \mid i \text{ est ami avec } j \}$$
Il existe deux membres qui ont le même nombre d’amis : $$\exists{\{i, j\}}\subseteq S, deg(i) = deg(j)$$
Il existe un nombre pair de membres ayant un nombre impair d’amis : $$\text{ Soit } I = \{ i \in S \mid \exist{k} \in \mathbb{Z} \land deg(i) = 2k + 1 \}, \exists{k’} \in \mathbb{Z} \text{ tel que } card(I) = 2k’ $$
Il existe deux membres qui ont le même nombre d’amis.
$$\exists{\{i, j\}}\subseteq S, deg(i) = deg(j)$$
Nous voulons prouver qu’il n’existe pas deux membres qui ont le même nombre d’amis :
$$\forall{\{i, j\}}\subseteq S, deg(i) \neq deg(j)$$
Soit $n$ le nombre de sommet du graphe $G, n = card(S)$ :
Nous avons un graphe de la forme : $deg(s_0) = 0, deg(s_1) = 1, …, deg(s_{n - 1}) = n - 1$.
Sachant que $deg(s) = card(adj(s))$, nous avons : $$adj(s_0) = \emptyset \text{ et } adj(s_{n - 1}) = S \setminus s_{n - 1}$$
Ce qui signifie que $s_{n - 1} \notin adj(s_0) \text{ et } s_0 \in adj(s_{n - 1})$, ce qui est absurde puisque la relation est symétrique.
Nous avons donc : $\exists{\{i, j\}}\subseteq S, deg(i) = deg(j)$.
$\square$
Il existe un nombre pair de membres ayant un nombre impair d’amis.
$$\text{ Soit } I = \{ i \in S \mid \exist{k} \in \mathbb{Z} \land deg(i) = 2k + 1 \}, \exists{k’} \in \mathbb{Z} \text{ tel que } card(I) = 2k’ $$
Puisque chaque arête part et arrive d’un noeud, nous avons :
$$ \sum_{s \in S}{deg(s)} = 2 \times card(A)$$
Nous définissons l’ensemble des membres ayant un nombre pair d’amis : $$\text{ Soit } P = \{ p \in S \mid \exist{k} \in \mathbb{Z} \land deg(i) = 2k \}$$
$I$ et $P$ forment une partition de $S~(I \cup P = S \land I \cap P = \emptyset)$, nous avons alors :
$$\sum_{s \in S}{deg(s)} = \sum_{i \in I}{deg(i)} + \sum_{p \in P}{deg(p)}$$ $$\sum_{s \in S}{deg(s)} = \sum_{i \in I}{(2k_i + 1)} + \sum_{p \in P}{2k_p}$$ $$\sum_{s \in S}{deg(s)} = 2\sum_{i \in I}{k_i} + \sum_{i \in I}{1} + 2\sum_{p \in P}{k_p}$$ $$\sum_{s \in S}{deg(s)} = 2(\sum_{i \in I}{k_i} + \sum_{p \in P}{k_p}) + \sum_{i \in I}{1}$$ $$\sum_{s \in S}{deg(s)} = 2(\sum_{i \in I}{k_i} + \sum_{p \in P}{k_p}) + card(I)$$
Or $\sum_{s \in S}{deg(s)}$ est pair et $2(\sum_{i \in I}{k_i} + \sum_{p \in P}{k_p})$ est pair également, ce qui implique que $card(I)$ est pair.
$\square$