Corrigé EDHEC 2026 Maths appliquées ECG — Problème, partie 2 (Q2.a à Q3.c) : Graphes de diamètre 2 et de degré maximal d : exemples à 4 et 5 sommets (cycles), au plus d voisins et majoration n ≤ d² + 1, graphes de Moore

Sujet officiel du concours EDHEC, session 2026, épreuve Maths appliquées ECG. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un « graphe » est ici simple (ni boucle, ni arête multiple), connexe, non orienté et non pondéré. Son ordre $n$ est son nombre de sommets ; $d$ est son degré maximal (le plus grand des degrés des sommets). La distance entre deux sommets est la longueur minimale d'une chaîne qui les relie ; le diamètre $D$ est la plus grande distance entre deux sommets distincts. $E_{n} (d)$ désigne l'ensemble des graphes d'ordre $n$ , de diamètre $D = 2$ et de degré maximal $d$ .

Q2. (a) Justifier que le graphe de sommets $1, 2, 3, 4$ et d'arêtes $12$ , $23$ , $34$ , $14$ appartient à $E_{4} (2)$ . (b) Parmi quatre graphes à $5$ sommets, $G_{1}$ (arêtes $12, 23, 34, 45, 15$ ), $G_{2}$ (arêtes $12, 13, 14, 15, 23, 34, 45$ ), $G_{3}$ (arêtes $13, 14, 24, 25, 35$ ) et $G_{4}$ (arêtes $12, 23, 14, 45$ ), dire lesquels sont dans $E_{5} (2)$ , en justifiant pour chacun.
Q3. Soit $G \in E_{n} (d)$ et $s$ un sommet de $G$ . (a) Montrer que $s$ a au plus $d$ voisins. (b) À l'aide de $D = 2$ , montrer que le nombre de sommets autres que $s$ est au plus $d + d (d - 1)$ . (c) Conclure que $n ⩽ d^{2} + 1$ .

Les graphes de $E_{n} (d)$ tels que $n = d^{2} + 1$ sont appelés graphes de Moore.

Corrigé

Q2. Les graphes de l'énoncé, redessinés :

(a) Le graphe a $4$ sommets ; il est simple et non orienté. Chaque sommet est extrémité d'exactement deux arêtes : $1$ (arêtes $12$ , $14$ ), $2$ ( $12$ , $23$ ), $3$ ( $23$ , $34$ ), $4$ ( $34$ , $14$ ). Le degré maximal est donc $d = 2$ . C'est le cycle $1 - 2 - 3 - 4 - 1$ ; il est connexe.

Distances : les paires ${1, 2}$ , ${2, 3}$ , ${3, 4}$ , ${1, 4}$ sont adjacentes (distance $1$ ). Les deux autres paires ne sont pas adjacentes et sont reliées par une chaîne de longueur $2$ : $1 - 2 - 3$ et $2 - 1 - 4$ ; leur distance vaut $2$ . La plus grande distance est $D = 2$ . Donc $ce graphe appartient a ˋ E_{4} (2) .$

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →