Degré

Définition 5.1   Le couple $(e, s)$ est un brin d'arête d'arête si l'arête $e$ a pour extrémité le sommet $s$.

Définition 5.2   Le degré d'un sommet $s$, noté $d(s)$, est le nombre de brins d'arêtes ayant $s$ comme extrémité.

Une boucle compte alors deux fois. Dans la figure 5.1, $d(A) = 1$, $d(B) = 3$, $d(C) = 4$, $d(D) = 2$, $d(E) = 0$, $d(F) = 2$,

Figure: Notion de degré

Théorème 5.1   Pour un graphe $G$ ayant au moins un sommet,
  $\sum_{s \in V(G)} d(s) = 2\vert E(G)\vert$

Ce théorème nous dit que si nous calculons la somme des degrés des sommets d'un graphe ayant au moins un sommet, alors on obtient le même nombre que si l'on multiplie par deux le nombre d'arêtes du graphe.

C'est un théorème qui semble évident. En effet, chaque arête apporte deux brins, à deux sommets (éventuellement les mêmes) quelque part dans le graphe. Mais le fait qu'un énoncé semble évident ne garantit pas sa véracité. En fait, la langue nous trompe souvent. Il faut donc essayer de trouver une méthode un peu plus formelle, en d'autres termes, une preuve.

Pour cela, nous allons utiliser une technique de preuve très souvent utilisée en informatique : la preuve par induction sur $\mathbb{N}$ ou preuve par récurrence. Une preuve par induction contient deux parties : le cas de base et la partie d'induction.

Pour notre preuve, nous allons alors construire un graphe donné en commençant par les sommets uniquement, puis rajouter à chaque étape une seule arête. L'idée est donc la suivante :

1. vérifier que $\sum_{s \in V} d(s) = 2\vert E\vert$ pour un graphe sans arête;
2. supposer que $\sum_{s \in V} d(s) = 2\vert E\vert$ pour n'importe quel graphe avec au plus $k$ arêtes;
3. prouver que si $\sum_{s \in V} d(s) = 2\vert E\vert$ est vrai pour n'importe quel graphe avec au plus $k$ arêtes, c'est aussi vrai pour n'importe quel graphe avec $k+1$ arêtes.

Si on y arrive, on sait donc que c'est vrai pour un graphe avec zéro arête. C'est donc vrai pour un graphe avec au plus $0$ arête, à savoir $k=0$. Mais nous avons prouvé que si c'est vrai pour un graphe avec au plus $0$ arête, c'est aussi vrai pour un graphe avec $1$ arête. Maintenant, nous savons que c'est vrai pour tous les graphes avec au plus $1$ arête. Mais dans ce cas, c'est aussi vrai pour un graphe avec $2$ arêtes, etc. Finalement, on peut conclure que c'est vrai pour les graphes avec un nombre quelconque d'arêtes.

Voyons maintenant un peu plus formellement comment faire :

Preuve :(du théoreme 5.1)
Par induction sur le nombre d'arêtes du graphe.

1. (cas de base) La propriété est trivialement vraie pour un graphe avec $\vert E\vert = 0$, car le degré de chaque sommet du graphe est $0$.
2. (hypothèse d'induction) On suppose que pour un graphe $G$ avec au moins un sommet et au plus $k$ arêtes, $\sum_{s \in V(G)} d(s) = 2\vert E(G)\vert$.
3. (induction) Nous construisons un graphe $G'$ en rajoutant une arête à $G$. Les extrémités de la nouvelle arête, disons $s_1$ et $s_2$ (il est possible que $s_1$ et $s_2$ soient le même sommet) vont avoir leur degré augmenté de $1$ chacun. Il est donc vrai que $\sum_{s \in V(G')} d(s) = \sum_{s \in V(G)} d(s) + 2$. De plus, nous avons rajouté une arête dans $G'$. Par conséquent $\vert E(G')\vert = \vert E(G)\vert + 1$. Donc, $\sum_{s \in V(G')} d(s) = \sum_{s \in V(G)} d(s) + 2 = 2\vert E(G)\vert + 2 = 2(\vert E(G)\vert + 1) = 2\vert E(G')\vert$. Nous avons donc $\sum_{s \in V(G')} d(s) = 2\vert E(G')\vert$

Nous avons donc prouvé la propriété par récurrence. height4pt width4pt