Graphes — vocabulaire et propriétés

Exercice 1 — Vocabulaire et lemme des poignées de mains
Corrigé :
a) Ordre $= 5$ (5 sommets) ; Taille $= 6$ (6 arêtes).
b) $d(1)=2$, $d(2)=3$, $d(3)=3$, $d(4)=2$, $d(5)=2$. Somme $= 2+3+3+2+2 = 12 = 2 \times 6 = 2m$. ✓
c) Les sommets 2 et 3 ont degré 3 (impair) : il y en a 2, qui est bien un nombre pair. Cela est conforme au corollaire du lemme des poignées de mains.

Exercice 2 — Chaînes, cycles et connexité
Corrigé :
a) On vérifie les arêtes : $\{1,2\} \in E$, $\{2,4\} \in E$, $\{4,5\} \in E$, $\{5,3\} \in E$, $\{3,1\} \in E$. Toutes présentes et le départ = l'arrivée = 1 : c'est bien un cycle. Longueur = 5 (5 arêtes).
b) La suite $1, 2, 3, 2, 4$ visite le sommet 2 deux fois (en positions 2 et 4) : elle n'est pas élémentaire.
c) Oui, $G$ est connexe. Par exemple, tout sommet est atteignable depuis 1 : $1-2-4$, $1-3-5$, etc. On peut construire un chemin entre n'importe quelle paire de sommets.

Exercice 3 — Graphes orientés
Corrigé :
a)
$d^+(A)=2$, $d^-(A)=0$ ; $d^+(B)=1$, $d^-(B)=2$ ; $d^+(C)=1$, $d^-(C)=2$ ; $d^+(D)=1$, $d^-(D)=1$.
b) $\sum d^+ = 2+1+1+1 = 5 = |A|$ ✓ ; $\sum d^- = 0+2+2+1 = 5 = |A|$ ✓.
c) Le graphe sous-jacent est connexe (toutes les arêtes $\{A,B\},\{A,C\},\{B,D\},\{B,C\},\{C,D\}$ connectent les 4 sommets). En revanche, $D$ n'est pas fortement connexe car il n'existe aucun chemin orienté arrivant à $A$ (son demi-degré intérieur est 0) : on ne peut pas revenir à $A$ depuis $B$, $C$ ou $D$.

Exercice 4 — Graphes particuliers et théorème d'Euler
Corrigé :
a) Dans $K_4$, chaque sommet a degré $4-1=3$ (impair). Comme il existe des sommets de degré impair, $K_4$ n'est pas eulérien.
b) Dans $K_5$, chaque sommet a degré $5-1=4$ (pair). $K_5$ est connexe : par le théorème d'Euler, $K_5$ est eulérien.
c) Le degré de chaque sommet dans $K_n$ est $n-1$. Pour que tous les degrés soient pairs, il faut que $n-1$ soit pair, c'est-à-dire $n$ impair. Donc $K_n$ est eulérien si et seulement si $n$ est impair et $n \ge 3$.

Exercice 5 — Modélisation et connexité
Corrigé :
a) Somme des degrés $= 3 \times 6 = 18 = 2m$, donc $m = 9$ arêtes.
b) Non, ce réseau ne peut pas être eulérien. Le graphe est 3-régulier : tous les sommets ont degré 3, qui est impair. Or un graphe eulérien doit avoir tous ses sommets de degré pair : la condition n'est pas satisfaite.