Combien d'arêtes au maximum ?

Exercice d'entraînement · niveau 2 · mathématiques appliquées (ECG 1re année), chapitre 3 — Théorie des graphes · Degrés et formule d'Euler

Énoncé

Soit $G$ un graphe non orienté sans boucle à $n$ sommets et $m$ arêtes. Montrer que $m \leq \frac{n ( n - 1 )}{2}$ , avec égalité si et seulement si $G$ est complet. Si $G$ désigne le graphe où deux sommets distincts sont reliés exactement lorsqu'ils ne le sont pas dans $G$ , exprimer son nombre d'arêtes et le degré de chacun de ses sommets.

Corrigé

La majoration. Une arête de $G$ relie deux sommets distincts (il n'y a pas de boucle), et deux sommets sont reliés par au plus une arête. L'application qui à une arête associe la paire de ses extrémités est donc injective, à valeurs dans l'ensemble des paires de sommets distincts. Or il y a $\frac{n ( n - 1 )}{2}$ telles paires : on choisit une extrémité ( $n$ façons), puis l'autre ( $n - 1$ façons), et chaque paire est ainsi comptée deux fois. D'où $m \leq \frac{n ( n - 1 )}{2} .$

Le cas d'égalité. L'égalité a lieu exactement lorsque l'application ci-dessus est aussi surjective, c'est-à-dire lorsque toute paire de sommets distincts porte une arête : c'est la définition du graphe complet $K_{n}$ .

Le graphe complémentaire. Chaque paire de sommets distincts porte une arête dans $G$ ou dans $G$ , et jamais dans les deux. Les nombres d'arêtes s'ajoutent donc pour donner le total des paires : $m + m = \frac{n ( n - 1 )}{2}, soit m = \frac{n ( n - 1 )}{2} - m .$

Les degrés. Fixons un sommet $s$ . Il y a $n - 1$ autres sommets ; chacun est soit voisin de $s$ dans $G$ , soit voisin de $s$ dans $G$ , exclusivement. Donc $de g_{G} (s) = n - 1 - de g_{G} (s) .$

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.