Vocabulaire et propriétés

Un graphe est donné par le tableau des voisins de chacun de ses sommets.

1. Ordre du graphe :
   Le graphe a six sommets, A, B, C, D, E et F : son ordre est $6$.
2. Nombre d’arêtes :
   En parcourant le tableau sans compter deux fois une même liaison : A–B, A–C, B–D, B–E, C–D, C–E, D–F et E–F, soit $8$ arêtes. Chaque liaison apparaît deux fois dans le tableau (A–B dans la ligne de A et dans celle de B).
3. Justifier que ce graphe n’est pas complet, puis donner le nombre d’arêtes qu’il faudrait lui ajouter pour obtenir le graphe complet d’ordre $6$ :
   Rédaction attendue. Dans un graphe complet, deux sommets distincts sont toujours adjacents ; ici, A et D ne sont pas adjacents, donc le graphe n’est pas complet. Le graphe complet d’ordre $6$ a ${\displaystyle \frac{6\times 5}{2}}=15$ arêtes ; il en manque $15-8=7$.

Graphes complets.

1. Nombre d’arêtes de $K_9$ :
   Chaque arête relie une paire de sommets : ${\displaystyle \frac{9\times 8}{2}}=36$.
2. Nombre d’arêtes de $K_{20}$ :
   ${\displaystyle \frac{20\times 19}{2}}=190$. Le nombre d’arêtes de $K_n$ grandit à peu près comme ${\displaystyle \frac{n^2}{2}}$.
3. Ordre du graphe complet qui possède $105$ arêtes :
   On cherche $n$ tel que ${\displaystyle \frac{n(n-1)}{2}}=105$, soit $n(n-1)=210=15\times 14$. L’ordre est $15$ (la fonction $n\mapsto n(n-1)$ est croissante pour $n⩾1$, la solution est unique).

Les sommets d’un graphe sont les entiers de $1$ à $8$ ; deux entiers distincts sont adjacents lorsque leur somme est un nombre premier.

1. Nombre d’arêtes :
   Les nombres premiers possibles sont $3$, $5$, $7$, $11$ et $13$ (la somme est au plus $7+8=15$). Arêtes : 1–2, 1–4, 1–6, 2–3, 2–5, 3–4, 3–8, 4–7, 5–6, 5–8, 6–7, soit $11$ arêtes.
2. Démontrer que deux entiers de même parité ne sont jamais adjacents. En déduire le nombre de triangles du graphe :
   Rédaction attendue. La somme de deux entiers de même parité est paire ; elle vaut au moins $1+3=4$, donc c’est un nombre pair supérieur à $2$, qui n’est pas premier : ces deux entiers ne sont pas adjacents. Parmi trois entiers, deux au moins ont la même parité : trois sommets ne sont jamais deux à deux adjacents. Le graphe n’a aucun triangle.
3. Nombre d’arêtes qu’il faudrait ajouter pour obtenir $K_8$ :
   $K_8$ a ${\displaystyle \frac{8\times 7}{2}}=28$ arêtes, et $28-11=17$.

Dans cet exercice, les graphes sont simples (ni boucle, ni arête multiple).

1. Démontrer qu’un graphe simple d’ordre $n$ a au plus ${\displaystyle \frac{n(n-1)}{2}}$ arêtes. Pour $n=12$, cette borne vaut
   Rédaction attendue. Dans un graphe simple, chaque arête relie deux sommets distincts, et deux arêtes différentes ne relient pas la même paire (pas d’arête multiple). Le nombre d’arêtes est donc au plus égal au nombre de paires de sommets, ${\displaystyle \left(\genfrac{}{}{0ex}{}{n}{2}\right)}={\displaystyle \frac{n(n-1)}{2}}$, avec égalité pour le graphe complet $K_n$. Pour $n=12$ : ${\displaystyle \frac{12\times 11}{2}}=66$.
2. Nombre de triangles de $K_7$ :
   Dans $K_7$, trois sommets quelconques sont deux à deux adjacents : un triangle revient à choisir $3$ sommets parmi $7$, soit ${\displaystyle \left(\genfrac{}{}{0ex}{}{7}{3}\right)}$ $={\displaystyle \frac{7\times 6\times 5}{3\times 2\times 1}}$ $=35$ triangles.
3. Un graphe simple d’ordre $7$ a $19$ arêtes. Nombre de paires de sommets non adjacents :
   Il y a ${\displaystyle \left(\genfrac{}{}{0ex}{}{7}{2}\right)}=21$ paires de sommets, et $19$ d’entre elles sont reliées par une arête : il reste $21-19=2$ paires de sommets non adjacents.

Un graphe a pour sommets A, B, C, D, E, F, G et pour arêtes A–B, A–C, A–F, B–C, B–D, B–G, C–D, C–E, D–E, D–G, E–F et F–G.

1. $d(B)=$
   B a pour voisins A, C, D et G : $d(B)=4$.
2. Somme des degrés de tous les sommets :
   $d(A)=3$, $d(B)=4$, $d(C)=4$, $d(D)=4$, $d(E)=3$, $d(F)=3$, $d(G)=3$, de somme $24$. Le lemme des poignées de main donne $2m=24$ : on retrouve bien les $12$ arêtes de la liste.
3. Nombre de sommets de degré impair :
   A, E, F et G sont de degré $3$ : il y en a $4$, un nombre pair, comme l’annonce le cours.

Utiliser le lemme des poignées de main.

1. Un graphe a $13$ arêtes et tous ses sommets sont de degré $2$. Son ordre est
   Si l’ordre est $n$, la somme des degrés vaut $2n$, et le lemme donne $2n=2\times 13$, d’où $n=13$.
2. Un graphe a $22$ arêtes et tous ses sommets sont de degré $4$. Son ordre est
   $4n=2\times 22=44$, donc $n=11$.
3. Un graphe d’ordre $7$ aurait tous ses sommets de degré $3$. Somme des degrés :
   $7\times 3=21$. Cette somme devrait valoir $2m$, donc être paire : un tel graphe n’existe pas.

Modéliser, puis appliquer le lemme des poignées de main.

1. Dans une classe de $25$ élèves, chacun voudrait échanger son numéro de téléphone avec exactement $7$ camarades. Justifier que c’est impossible. Somme des degrés du graphe associé :
   Rédaction attendue. On modélise par un graphe : les sommets sont les $25$ élèves, et une arête relie deux élèves qui ont échangé leurs numéros. Chaque sommet serait de degré $7$, donc la somme des degrés vaudrait $25\times 7=175$. D’après le lemme des poignées de main, cette somme vaut $2m$ : elle est paire. Comme $175$ est impair, la situation est impossible.
2. Un graphe a $12$ arêtes ; trois sommets sont de degré $4$, deux sont de degré $3$ et tous les autres de degré $2$. Nombre de sommets de degré $2$ :
   Si $x$ sommets sont de degré $2$, la somme des degrés vaut $3\times 4+2\times 3+2x=18+2x$. Le lemme donne $18+2x=24$, d’où $x=3$.
3. Ordre de ce graphe :
   $3+2+3=8$ sommets.

Dans cet exercice, les graphes sont simples.

1. Dans un graphe simple d’ordre $9$, le degré d’un sommet est un entier compris entre $0$ et
   Un sommet peut être adjacent à chacun des $8$ autres sommets, et à aucun autre (ni boucle, ni arête multiple) : son degré est compris entre $0$ et $8$.
2. Démontrer que, dans un graphe simple d’ordre $n⩾2$, deux sommets au moins ont le même degré. Pour $n=6$, nombre de valeurs que les degrés peuvent prendre simultanément, au plus :
   Rédaction attendue. Les degrés sont des entiers de $0$ à $n-1$, soit $n$ valeurs. Mais les valeurs $0$ et $n-1$ ne peuvent pas être prises en même temps : un sommet de degré $n-1$ est adjacent à tous les autres, donc aucun sommet n’est isolé. Les $n$ sommets ont donc leurs degrés dans un ensemble d’au plus $n-1$ valeurs ($5$ pour $n=6$). Il y a plus de sommets que de valeurs possibles : deux sommets au moins ont le même degré (principe des tiroirs).
3. Un graphe d’ordre $7$ a six sommets de degré $3$. Le degré du septième sommet est-il pair ou impair ?
   Rédaction attendue. Le nombre de sommets de degré impair est toujours pair. Les six sommets de degré $3$ sont déjà en nombre pair ; si le septième était de degré impair, il y aurait $7$ sommets de degré impair, nombre impair : c’est impossible. Le septième sommet est de degré pair.

Quatre pages d’un site, $P_1$, $P_2$, $P_3$, $P_4$, sont reliées par des liens modélisés par les arcs $P_1\to P_2$, $P_1\to P_3$, $P_2\to P_3$, $P_3\to P_1$, $P_3\to P_4$ et $P_4\to P_2$.

1. Degré sortant de $P_3$ :
   Deux arcs partent de $P_3$ : $P_3\to P_1$ et $P_3\to P_4$.
2. Degré entrant de $P_2$ :
   Deux arcs arrivent en $P_2$ : $P_1\to P_2$ et $P_4\to P_2$.
3. Calculer la somme des degrés entrants et l’interpréter :
   Rédaction attendue. Degrés entrants : $P_1$ : $1$, $P_2$ : $2$, $P_3$ : $2$, $P_4$ : $1$, de somme $6$. Les degrés sortants ($2$, $1$, $2$, $1$) ont la même somme. C’est le nombre d’arcs : chaque arc est compté une fois comme sortant de son origine et une fois comme entrant en son extrémité.
4. Longueur du plus court chemin de $P_4$ vers $P_1$ :
   Le seul arc qui part de $P_4$ va vers $P_2$, et le seul qui part de $P_2$ va vers $P_3$ : tout chemin de $P_4$ vers $P_1$ commence donc par $P_4\to P_2\to P_3$ et a une longueur au moins égale à $3$ ; $P_4\to P_2\to P_3\to P_1$, de longueur $3$, est le plus court. On remarque aussi le circuit $P_1\to P_2\to P_3\to P_1$.

Un graphe orienté sans boucle a pour sommets A, B, C, D. Ses degrés sortants valent, dans l’ordre A, B, C, D : $2$, $1$, $3$ et $2$ ; ses degrés entrants valent $1$ pour A, $3$ pour B et $2$ pour D.

1. Degré entrant de C :
   Les deux sommes sont égales au nombre d’arcs : $2+1+3+2=8$, donc $1+3+d^{-}(C)+2=8$ et $d^{-}(C)=2$.
2. Si l’on oublie le sens des arcs, somme des degrés du graphe non orienté obtenu :
   Chaque sommet a pour degré $d^{+}+d^{-}$ ; la somme vaut $8+8=16$, le double du nombre d’arêtes, comme l’annonce le lemme des poignées de main.

Cinq carrefours A, B, C, D, E sont reliés par des rues à sens unique : A → B, B → C, C → A, A → D, C → D, D → E et B → E.

1. Le carrefour d’où l’on ne peut plus repartir est
   Aucun arc ne part de E : son degré sortant est nul.
2. Longueur du plus court chemin de A vers E :
   A n’est pas relié directement à E ; A → B → E et A → D → E sont des chemins de longueur $2$.
3. Démontrer que l’on peut aller de A à tous les autres carrefours. Nombre de carrefours, autres que A, depuis lesquels on peut revenir en A :
   Rédaction attendue. Depuis A : A → B, A → B → C, A → D et A → D → E ; tous les carrefours sont atteints. Pour revenir en A, il faut emprunter l’arc C → A, le seul qui arrive en A. On atteint C depuis B (B → C) ; en revanche, de D on ne peut aller qu’en E, et de E nulle part. Seuls B et C permettent de revenir en A : il y en a $2$.

Les sommets d’un graphe orienté sont les entiers de $0$ à $7$. De chaque sommet $n$ part un seul arc, qui va vers le reste de la division euclidienne de $3n+1$ par $8$.

1. L’arc qui part de $5$ arrive en
   $3\times 5+1=16=2\times 8+0$ : le reste est $0$.
2. En partant de $0$, on revient en $0$ pour la première fois après un chemin de longueur
   $0\to 1\to 4\to 5\to 0$ : $3\times 0+1=1$, $3\times 1+1=4$, $3\times 4+1=13$ (reste $5$), $3\times 5+1=16$ (reste $0$). Le circuit a pour longueur $4$.
3. Démontrer que tout graphe orienté fini dont chaque sommet a un degré sortant au moins égal à $1$ contient un circuit. Nombre de circuits du graphe de cet exercice :
   Rédaction attendue. Partons d’un sommet $s_0$ et suivons à chaque étape un arc qui sort du sommet atteint : c’est toujours possible, puisque chaque degré sortant vaut au moins $1$. On obtient une suite $s_0,s_1,s_2,\dots$ ; le graphe n’ayant qu’un nombre fini de sommets, un sommet revient : soit $j$ le premier rang tel que $s_j$ soit égal à un sommet déjà rencontré $s_i$ ($i<j$). Alors $s_i\to s_{i+1}\to \cdots \to s_j$ $=s_i$ est un chemin fermé, de longueur non nulle, dont les sommets $s_i,\dots ,s_{j-1}$ sont distincts : il n’emprunte pas deux fois le même arc, c’est un circuit. Ici, les arcs donnent $0\to 1\to 4\to 5\to 0$ et $2\to 7\to 6\to 3\to 2$ : chaque sommet est dans l’un de ces deux circuits, et il n’en part qu’un arc, donc le graphe a exactement $2$ circuits.

Un graphe a pour sommets A, B, C, D, E, F et pour arêtes A–B, A–C, A–D, B–C, C–D, D–E et E–F.

1. Longueur de la chaîne F–E–D–C–A–B :
   Elle emprunte F–E, E–D, D–C, C–A et A–B : $5$ arêtes (pour $6$ sommets).
2. Longueur de la plus courte chaîne reliant F à B :
   F n’a qu’un voisin, E, qui n’a pour autres voisins que D ; D n’est pas adjacent à B. Il faut donc au moins $4$ arêtes, et F–E–D–A–B en a $4$.
3. Longueur du plus petit cycle passant par D :
   D–A–C–D est un cycle de longueur $3$ (arêtes D–A, A–C et C–D) ; un cycle d’un graphe simple a au moins $3$ arêtes.

Neuf îles A, B, C, D, E, F, G, H, I sont reliées par des liaisons maritimes : A–E, E–H, H–A, B–G, G–D, C–F et F–I.

1. Nombre de composantes connexes du graphe :
   Les composantes connexes sont {A, E, H}, {B, D, G} et {C, F, I} : aucune liaison ne relie deux de ces groupes.
2. Déterminer, en justifiant, le nombre minimal de liaisons à créer pour pouvoir aller de n’importe quelle île à n’importe quelle autre :
   Rédaction attendue. Une liaison nouvelle relie deux îles ; elle réunit au plus deux composantes connexes en une seule, donc le nombre de composantes diminue d’au plus $1$. Pour passer de $3$ composantes à $1$, il faut au moins $2$ liaisons ; deux suffisent, par exemple A–B et B–C.

Un réseau de sept stations est modélisé par le graphe ci-dessous.

1. Démontrer que le graphe est connexe. Nombre d’arêtes :
   Rédaction attendue. Chaque station est reliée à A par une chaîne : A–B, A–C, A–B–D, A–C–E, A–C–D–F et A–C–D–F–G. Deux stations quelconques sont donc reliées par une chaîne passant par A : le graphe est connexe. Ses arêtes sont A–B, A–C, B–D, C–D, C–E, D–F, E–F et F–G, soit $8$ arêtes.
2. Démontrer que la plus courte chaîne reliant A à G a pour longueur
   Rédaction attendue. La chaîne A–C–D–F–G est de longueur $4$. Montrons qu’il n’y en a pas de plus courte. Le seul voisin de G est F : toute chaîne qui arrive en G passe par F juste avant. Les voisins de F sont D, E et G, et A n’est adjacent ni à D ni à E ; aucune chaîne A–x–F n’existe, donc aucune chaîne de A à G de longueur $3$ ou moins. La plus courte chaîne a pour longueur $4$.
3. Longueur du plus long cycle du graphe :
   A–B–D–F–E–C–A emprunte A–B, B–D, D–F, F–E, E–C et C–A : c’est un cycle de longueur $6$. On ne peut pas faire mieux : un cycle n’emprunte pas F–G (arrivé en G, qui n’a qu’un voisin, il ne pourrait pas repartir) ; à chaque passage par un sommet, il utilise deux de ses arêtes, donc il en utilise un nombre pair en chaque sommet. En C, de degré $3$, il en utilise au plus $2$ : il laisse de côté au moins une des $7$ arêtes autres que F–G, et sa longueur est au plus $6$. Les deux autres cycles, A–B–D–C–A et C–D–F–E–C, ont pour longueur $4$.

Un graphe simple d’ordre $9$ a tous ses sommets de degré au moins égal à $4$. On considère deux sommets $u$ et $v$ non adjacents.

1. Le nombre de voisins de $u$ ajouté au nombre de voisins de $v$ vaut au moins
   $d(u)+d(v)⩾4+4=8$.
2. Ces voisins sont tous choisis parmi un ensemble de combien de sommets ?
   $u$ et $v$ ne sont pas adjacents : leurs voisins sont parmi les $9-2=7$ autres sommets.
3. Démontrer que le graphe est connexe. Deux sommets quelconques sont reliés par une chaîne de longueur au plus
   Rédaction attendue. Soient $u$ et $v$ deux sommets distincts. S’ils sont adjacents, la chaîne $u$–$v$ a pour longueur $1$. Sinon, on compte au moins $8$ voisins (de $u$ ou de $v$) répartis parmi seulement $7$ sommets : un sommet $w$ est compté deux fois, c’est un voisin commun. La chaîne $u$–$w$–$v$ a pour longueur $2$. Deux sommets quelconques sont reliés par une chaîne de longueur au plus $2$ : le graphe est connexe.

Appliquer le théorème d’Euler.

1. $K_7$ admet un cycle eulérien. Sa longueur est
   $K_7$ est connexe et ses sommets sont tous de degré $6$, pair : il admet un cycle eulérien. Sa longueur est le nombre d’arêtes, ${\displaystyle \frac{7\times 6}{2}}=21$.
2. Nombre de sommets de degré impair de $K_8$ :
   Les $8$ sommets de $K_8$ sont de degré $7$, impair. Ce n’est ni $0$ ni $2$ : $K_8$ n’a ni cycle ni chaîne eulérienne.
3. Un graphe connexe a pour sommets A, B, C, D, E, F, de degrés respectifs $2$, $4$, $3$, $3$, $2$, $4$. Une chaîne eulérienne part de C ; elle se termine en
   Exactement deux sommets sont de degré impair, C et D : d’après le théorème d’Euler, toute chaîne eulérienne a pour extrémités C et D.

Le plan d’un musée est modélisé par un graphe : les sommets sont les salles, les arêtes les passages.

1. Justifier qu’aucun visiteur ne peut emprunter chaque passage une fois et une seule. Nombre de salles de degré impair :
   Rédaction attendue. Chaque salle est reliée à M : M–N, M–O, M–P, M–O–Q et M–P–R ; le graphe est connexe. Les degrés valent $d(M)=3$, $d(N)=3$, $d(O)=3$, $d(P)=3$, $d(Q)=2$ et $d(R)=2$ : quatre salles sont de degré impair. Le théorème d’Euler demande $0$ ou $2$ sommets de degré impair : un tel parcours n’existe pas.
2. On perce un nouveau passage entre O et P. Le parcours empruntant chaque passage une fois part maintenant de M ; il se termine en
   Rédaction attendue. Le passage O–P augmente de $1$ les degrés de O et de P, qui deviennent $4$. Seuls M et N restent de degré impair ; le graphe est toujours connexe. D’après le théorème d’Euler, il existe une chaîne eulérienne d’extrémités M et N : partie de M, elle se termine en N. Par exemple M–O–Q–R–P–O–N–P–M–N.
3. Nombre de passages empruntés par ce parcours :
   Le graphe a maintenant $8+1=9$ arêtes. Le parcours M–O–Q–R–P–O–N–P–M–N emprunte M–O, O–Q, Q–R, R–P, P–O, O–N, N–P, P–M et M–N : les $9$ passages, chacun une fois.

Un graphe simple a pour sommets u, v, w, x, y, z et pour arêtes u–v, u–w, v–w, x–y, x–z et y–z.

1. Un élève affirme : « tous les degrés sont pairs, donc ce graphe admet un cycle eulérien ». Expliquer son erreur. Nombre de composantes connexes :
   Rédaction attendue. Chaque sommet a deux voisins, tous les degrés valent $2$. Mais le graphe est formé de deux triangles, u–v–w et x–y–z, sans arête entre eux : il a $2$ composantes connexes. Le théorème d’Euler suppose le graphe connexe ; ici, un cycle eulérien devrait passer d’un triangle à l’autre, ce qu’aucune arête ne permet. L’élève a oublié de vérifier la connexité.
2. Démontrer qu’il faut ajouter au moins quatre arêtes (sans créer d’arête multiple) pour que le graphe admette un cycle eulérien. Avec u–x, x–v, v–y et y–u, longueur de ce cycle :
   Rédaction attendue. Les sommets d’un même triangle sont déjà adjacents : toute arête ajoutée relie un sommet de {u, v, w} à un sommet de {x, y, z}, et il en faut au moins une pour rendre le graphe connexe. Après l’ajout, tous les degrés doivent rester pairs : chaque sommet touché par les nouvelles arêtes en reçoit un nombre pair, donc au moins $2$. Soit $a$ un sommet du premier triangle touché : il reçoit deux nouvelles arêtes, vers deux sommets $b$ et $c$ de l’autre triangle. À son tour, $b$ doit recevoir une seconde nouvelle arête, vers un sommet du premier triangle autre que $a$ (pas d’arête multiple), et de même pour $c$. Ces quatre arêtes sont distinctes : il en faut au moins $4$. Avec u–x, x–v, v–y et y–u, les degrés de u, v, x, y passent à $4$, ceux de w et z restent à $2$, et le graphe est connexe : d’après le théorème d’Euler, il admet un cycle eulérien, de longueur $6+4=10$.

Une « roue » est formée d’un moyeu H relié à six sommets numérotés de $1$ à $6$, qui forment eux-mêmes le cycle 1–2–3–4–5–6–1.

1. Nombre d’arêtes de la roue :
   $6$ rayons (H–1, …, H–6) et $6$ arêtes du cycle : $12$ arêtes. Contrôle : $d(H)=6$ et les six autres sommets sont de degré $3$, de somme $6+18=24=2\times 12$.
2. Nombre de sommets de degré impair :
   Les sommets $1$ à $6$ sont de degré $3$ (deux voisins sur le cycle et le moyeu) ; H est de degré $6$. Il y a $6$ sommets de degré impair : la roue n’a ni cycle ni chaîne eulérienne.
3. Démontrer qu’il faut ajouter au moins trois arêtes (sans arête multiple) pour obtenir un cycle eulérien. Avec 1–4, 2–5 et 3–6, longueur de ce cycle :
   Rédaction attendue. Une arête ajoutée change la parité du degré de ses deux extrémités seulement : elle rend pairs au plus deux des six sommets de degré impair. Pour que les six deviennent pairs, il faut au moins ${\displaystyle \frac{6}{2}}=3$ arêtes. Les arêtes 1–4, 2–5 et 3–6 relient des sommets non adjacents (pas d’arête multiple) et portent les degrés de $1$ à $6$ à $4$ ; H reste de degré $6$. Le graphe est connexe et tous ses degrés sont pairs : d’après le théorème d’Euler, il admet un cycle eulérien, de longueur $12+3=15$.