Vocabulaire et propriétés

1. a)Le graphe a six sommets, A, B, C, D, E et F : il est d’ordre $6$. En lisant le tableau sans compter deux fois une même liaison, ses arêtes sont A–B, A–C, A–F, B–C, B–D, B–E, C–D, D–E et E–F, soit $9$ arêtes. (1)
2. b)Le degré d’un sommet est son nombre de voisins : $d(A)=3$, $d(B)=4$, $d(C)=3$, $d(D)=3$, $d(E)=3$ et $d(F)=2$. La somme des degrés vaut $3+4+3+3+3+2=18$, et $2m=2\times 9=18$ : le lemme des poignées de main est vérifié. (1)
3. c)Non. Dans le graphe complet d’ordre $6$, chaque sommet serait adjacent aux $5$ autres, donc de degré $5$ ; or $d(F)=2$. Autre justification : $K_6$ a ${\displaystyle \frac{6\times 5}{2}}=15$ arêtes, et ce graphe n’en a que $9$. (1)
4. d)Dans un groupe de quatre sommets deux à deux adjacents, chaque sommet a au moins $3$ voisins, ce qui exclut F ($d(F)=2$). Il reste A, B, C, D, E, et il faut en choisir quatre, donc écarter un seul sommet. Or A n’est adjacent ni à D ni à E, et C n’est pas adjacent à E : pour éviter la paire A, D et la paire A, E, il faudrait écarter A ; il resterait B, C, D, E, qui contient la paire non adjacente C, E. Aucun groupe de quatre sommets deux à deux adjacents n’existe. Le graphe contient en revanche des triangles : A–B–C, B–C–D et B–D–E. (1)

Repère — La somme des degrés contrôle toujours la liste des arêtes : elle vaut le double de leur nombre.

1. a)Degrés sortants : $d^{+}(X)=2$, $d^{+}(Y)=1$, $d^{+}(Z)=1$, $d^{+}(T)=2$, $d^{+}(U)=1$. Degrés entrants : $d^{-}(X)=1$ (T → X), $d^{-}(Y)=2$ (X → Y et U → Y), $d^{-}(Z)=2$ (X → Z et Y → Z), $d^{-}(T)=1$ (Z → T), $d^{-}(U)=1$ (T → U). (1)
2. b)Somme des degrés sortants : $2+1+1+2+1=7$ ; somme des degrés entrants : $1+2+2+1+1=7$. Les deux sommes sont égales au nombre d’arcs, $7$ : chaque arc est compté une fois comme sortant de son origine et une fois comme entrant en son extrémité. (1)
3. c)X → Z → T → X emprunte les arcs X → Z, Z → T et T → X, dans le bon sens, et revient en X : c’est un circuit de longueur $3$. X → Y → Z → T → X emprunte X → Y, Y → Z, Z → T et T → X : c’est un circuit de longueur $4$. (1)
4. d)U → Y → Z → T → X est un chemin de longueur $4$. Il n’y en a pas de plus court : le seul arc qui part de U va vers Y, le seul qui part de Y va vers Z, le seul qui part de Z va vers T ; on est donc obligé de passer par Y, Z puis T, et seul T mène à X. Le plus court chemin de U vers X a pour longueur $4$. (1)

Repère — Dans un graphe orienté, un chemin suit les flèches, et la somme des degrés entrants vaut le nombre d’arcs.

1. a)Depuis $1$, on atteint $2$ et $3$, puis $4$ (par $3$), et aucune arête ne sort de {1, 2, 3, 4} vers les autres sommets. Depuis $5$, on atteint $6$, $7$ et $8$. Les composantes connexes sont {1, 2, 3, 4} et {5, 6, 7, 8} : aucune chaîne ne relie $1$ à $5$, le graphe n’est pas connexe. (1)
2. b)1–2–3–1 est une chaîne fermée qui emprunte trois arêtes distinctes (1–2, 2–3, 3–1) : c’est un cycle de longueur $3$. 5–6–7–8–5 emprunte 5–6, 6–7, 7–8 et 8–5 : c’est un cycle de longueur $4$. (1)
3. c)Oui. Ses arêtes 4–3, 3–1, 1–2 et 2–3 existent et sont deux à deux distinctes : c’est une chaîne simple, de longueur $4$. Elle repasse par le sommet $3$, ce qui est permis : « simple » interdit seulement de réemprunter une arête. (1)
4. d)Avec l’arête 4–5, chaque sommet est relié à $3$ : $1$, $2$ et $4$ directement, puis $5$, $6$, $7$, $8$ par 3–4–5–… ; le graphe est connexe. Les degrés valent $d(1)=2$, $d(2)=2$, $d(3)=3$, $d(4)=2$, $d(5)=3$, $d(6)=2$, $d(7)=2$, $d(8)=2$ : exactement deux sommets impairs, $3$ et $5$. D’après le théorème d’Euler, il existe une chaîne eulérienne d’extrémités $3$ et $5$, par exemple 3–1–2–3–4–5–6–7–8–5, qui emprunte les $9$ arêtes une fois chacune. (1)

Repère — Une chaîne simple peut repasser par un sommet ; c’est une arête qu’elle ne réemprunte jamais.

1. a)Chaque attraction est reliée à P par une chaîne : P–Q, P–R, P–S, P–R–U et P–Q–T. Deux attractions quelconques sont donc reliées par une chaîne passant par P : le graphe est connexe. (1)
2. b)$d(P)=3$, $d(Q)=3$, $d(R)=3$, $d(S)=2$, $d(T)=3$ et $d(U)=2$. La somme vaut $16$ ; d’après le lemme des poignées de main, $2m=16$, donc il y a $8$ allées, ce que confirme la liste. (1)
3. c)Un tel parcours serait une chaîne eulérienne. Le graphe est connexe, mais il a quatre sommets de degré impair : P, Q, R et T. Le théorème d’Euler exige $0$ ou exactement $2$ sommets de degré impair : le visiteur ne peut pas emprunter chaque allée une fois et une seule. (1)
4. d)Fermer une allée diminue de $1$ le degré de ses deux extrémités. En fermant P–Q, P et Q deviennent de degré $2$ ; seuls R et T restent de degré impair, et le graphe reste connexe (P–R, R–Q, Q–T, T–S, T–U). D’après le théorème d’Euler, il existe une chaîne eulérienne d’extrémités R et T, par exemple R–P–S–T–U–R–Q–T, qui emprunte P–R, P–S, S–T, T–U, R–U, Q–R et Q–T : les $7$ allées restantes, une fois chacune. Fermer P–R, Q–R ou Q–T convient aussi : l’allée fermée doit relier deux des quatre sommets impairs, et le graphe reste connexe. (1)

Repère — Ajouter ou retirer une arête change la parité du degré de ses deux extrémités, et d’elles seules.

1. a)On modélise par un graphe : les sommets sont les $9$ joueurs, et une arête relie deux joueurs qui disputent une partie. Chaque sommet serait de degré $5$, et la somme des degrés vaudrait $9\times 5=45$. D’après le lemme des poignées de main, cette somme vaut $2m$ : elle est paire. Comme $45$ est impair, c’est impossible. (1)
2. b)La somme des degrés vaut $16\times 7=112$. D’après le lemme des poignées de main, $2m=112$, donc le graphe a $m=56$ arêtes. (1)
3. c)D’après le lemme des poignées de main, la somme de tous les degrés vaut $2m$, nombre pair. On la sépare en deux : la somme des degrés pairs, qui est paire, et la somme des degrés impairs. Par différence de deux nombres pairs, la somme des degrés impairs est paire. Or une somme de nombres impairs est paire si et seulement si elle compte un nombre pair de termes : le nombre de sommets de degré impair est pair. (1)
4. d)Si un graphe admet un cycle eulérien, la condition nécessaire du théorème d’Euler (démontrée dans le cours) donne : tous ses sommets sont de degré pair, il a $0$ sommet de degré impair. Une chaîne eulérienne non fermée exige exactement $2$ sommets de degré impair. Les deux situations s’excluent : le graphe n’a aucune chaîne eulérienne non fermée. L’élève confond « cycle eulérien », chaîne eulérienne fermée, et « chaîne eulérienne non fermée ». (1)

Repère — Lemme des poignées de main et théorème d’Euler reposent sur la même idée : compter les arêtes à leurs extrémités.