Correction exercice I

1. Nous procédons par récurrence sur la taille du graphe.
Supposons que \(\forall m \in N\), \(Em\) : Tout graphe G de taille \(m\) satisfait \(\sum\limits_{v \in V(G)} {{d_G}(v) = } 2m\)
• Pour \(m = 0\), G n’a aucune arête. Par conséquent, tout sommet de G a un degré nul
\(\forall v \in V(G)\), \({{d_G}(v) = }\) \(0\) et \({E_0}\) est donc vrai.
• Soit \(k\) un entier non nul, supposons que \({E_k}\) est vrai. Soit G un graphe de taille \(k + 1\), et soit \(e\) une arête de G, d’extrémités \(x\) et \(y\). Alors \(\left| {E(G)} \right| = \) \(\left| {E(G - e)} \right| + 1\). D’où \(\left| {E(G - e)} \right| = k\), or par hypothèse \(\sum\limits_{v \in V(G - e)} {{d_G} - e(v) = } \) \(2k\). Par ailleurs, \({d_G} - e(v) = \) \({d_G}(v) - 1\) pour \(v \in \{ x,y\} \) et \({d_G} - e(v) = \) \({d_G}(v)\) pour \(v \in V(G)\) \( - \{ x,y\} \)
Par conséquent \(\sum\limits_{v \in V(G - e)} {{d_G} - e(v) = } \) \(\sum\limits_{v \in V(G - e)} {{d_G} - 2 = } 2k\)
On en déduit que \(\sum\limits_{v \in V(G - e)} {{d_G} - e(v) = } \) \(2(k + 1)\). Ce qui veut dire que \({E_k} + 1\) est vrai.
Conclusion \({E_m}\) est vrai pour tout \(m \in \mathbb{N}\)
2. Montrons que le nombre de sommets de degré impair est pair
\(\left\{ \begin{array}{l}\left| V \right| = 5\\\left| E \right| = 8\end{array} \right.\)
• \(d(E) = 2\)
• \(d(B) = d(D) = 4\)
• \(d(D) = d(B) = 3\)
Nous avons donc deux sommets D et B de degré impair, la conséquence du lemme des poignées de mains est vérifiées.
3. La séquence de degré de ce graphe est : 4-4-3-3-2
Oui elle est graphique car :  Une suite décroissante d’entiers naturels est dite graphique s’il existe un graphe ayant cette suite pour séquence de degré.
4. Cette séquence n’est pas graphique car n’obéit pas à la conséquence du lemme des poignées de mains dit stipule que : « Dans un graphe simple G, le nombre de sommets de degré impair est pair Il y a ici trois degrés impair »

Correction exercice II

1. De tels tracés sont possibles si le graphe correspondant admet un chemin eulérien, c’est-à-dire s’il contient exactement 0 ou 2 sommets de degré impair.
La réponse est donc positive uniquement pour la deuxième figure (2)
2. Pour qu’un graphe soit eulérien, il faut et il suffit que tous ses sommets soient de degré pair. Si un graphe contient k sommets impairs, il est possible de rajouter un nouveau sommet x, relié à ces k sommets. Dans le graphe obtenu, les k sommets considérés sont devenus pairs… Cependant, le degré de x étant k, le graphe n’est toujours pas eulérien si k était impair… Remarquons qu’il est possible de rajouter des arêtes entre les sommets de degré impair dans le graphe d’origine… Mais l’ajout d’une telle arête, entre deux sommets impairs a et b par exemple, fait que le nombre de sommets impairs devient k-2, qui a la même parité que k…
La réponse est donc : ce n’est possible que si le nombre de sommets impairs est pair…
3. Désignons par 1,2,…,9 les 9 personnes et considérons le graphe complet à 9 sommets.
Une composition de la table correspond à un cycle hamiltonien (un cycle passant une et une seule fois par chaque sommet).
Si deux compositions de table correspondent à deux cycles ayant une arête commune, cela signifie que les deux personnes reliées par cette arête se retrouvent côte à côte… Ainsi, le problème revient à déterminer le nombre de cycles hamiltoniens disjoints.
Le graphe possédant \(\frac{{9 \times 8}}{2} = 36\) arêtes et chaque cycle utilisant 9 arêtes, ce nombre est au maximum égal à 4…
Il vaut effectivement 4, comme le prouvent les 4 cycles hamiltoniens disjoints suivants :
• 1, 2, 3, 9, 4, 8, 5, 7, 6
• 1, 3, 4, 2, 5, 9, 6, 8, 7
• 1, 4, 5, 3, 6, 1, 7, 9, 8
• 1, 5, 6, 4, 7, 2, 8, 1, 9

NB : Ces cycles hamiltoniens ne sont pas obtenus « par hasard »
En les observant attentivement, on peut remarquer qu’ils sont construits de la façon suivante :
• Premier cycle : 1,2,3,N,4,N-1,5,N-2,6,N-3,etc., où N représente le nombre total de sommets…
• Deuxième cycle : on conserve le « 1 » et on ajoute 1 aux autres éléments, avec la règle N+1 = 2. chaque cycle est alors obtenu du précédent en conservant le « 1 » et en ajoutant 1 aux autres éléments (toujours avec la règle N+1=2…