Correction exercice I

1.a) Les sommets de ce graphes sont : A, B, C, D et E
1.b) Les sommets adjacents sont : {A ;B}, {A ;C}, {A ;D}, {C ;D} et {C ;E}
1.c) Ce graphe n’a pas de sommet isolé.
1.d) L’ordre de ce graphe est : \(\left| V \right| = 5\)
2. La valence de chaque sommet
Graphe 1
a) Valence de chaque sommet
• \({d_{{G_1}}}(A) = 0\)
• \({d_{{G_1}}}(E) = \) \({d_{{G_1}}}(D) = 1\)
• \({d_{{G_1}}}(B) = \) \({d_{{G_1}}}(C) = 2\)
b) Ordre du graphe \(\left| V \right| = 5\)
c) La taille du graphe \(\left| E \right| = 3\)
Vérification avec le lemme des poignées de mains, en effet : \(\sum\limits_{v \in V({G_1})} {{d_{{G_1}}}(v) = } \) \(2\left| {E({G_1})} \right|\)
Ainsi \({d_{{G_1}}}(A) + {d_{{G_1}}}(B)\) \( + {d_{{G_1}}}(C) + {d_{{G_1}}}(E) + \) \({d_{{G_1}}}(D) = 0 + 2\) \( + 2 + 1 + 1 = \) \(6 = 2\left| E \right|\)
\(\left| E \right| = \frac{6}{2} = 3\)
Graphe 2
a) Valence de chaque sommet
\({d_{{G_2}}}(A) = {d_{{G_2}}}(B)\) \( = {d_{{G_2}}}(C) = {d_{{G_2}}}(D)\) \( = {d_{{G_2}}}(E) = {d_{{G_1}}}(F)\) \( = 5\)
b) Ordre du graphe \(\left| V \right| = 6\)
c) La taille du graphe \(\left| E \right| = 15\)
Vérification avec le lemme des poignées de mains : \(\sum\limits_{v \in V({G_2})} {{d_{{G_2}}}(v) = } \) \(2\left| {E({G_2})} \right|\)
\(\sum\limits_{v \in V({G_2})} {{d_{{G_2}}}(v) = } \) \(5 \times 6 = 2\left| {E({G_2})} \right|\) \( \Rightarrow \left| {E({G_2})} \right| = \) \(\frac{{30}}{2} = 15\)
Graphe 3
A chercher

Correction exercice II

1. Construisons un graphe représentant toutes les parties possibles.
2. Nombre de match que doit livrer

NB : L’ordre du graphe représente le nombre de joueur, la taille, le nombre de match et la valence d’un sommet le nombre de match livré par joueur.

D’après le graphe et Le lemme de poignée de main
\(\sum\limits_{v \in V(G)0} {{d_G}(v) = } 5\) \( \times 6 = 30 = 2\) \(\left| {E(G)} \right|\)
Soit \(\left| {E(G)} \right| = \frac{{30}}{2} = 15\) matchs

3. Nombre de matchs on doit livrer pour la première phase ?
\(\sum\limits_{v \in V(G)0} {{d_G}(v) = } \) \(5 \times 6 = 30\)

Correction exercice III

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 P
\(\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 IV

1. La réunion représente un graphe dont les sommets sont constitués des membres. Nous aurions dont 5 sommets \(\left| V \right| = 5\), chaque membre saluant les 4 autres,
\(d(1) = d(2)\) \( = d(3) = d(4)\) \( = d(5) = 4\)
D’après le lemme des poignées de mains, ils ont échangé
\(\sum\limits_{} {d(v) = } \) \(4 \times 5 = 2\left| E \right|\) \( \Rightarrow \left| E \right| = \frac{{4 \times 5}}{2} = 10\)
Ils ont donc échangé 10 poignées de mains
• Si la réunion a 35 membres
\(d(1) = ... = \) \(d(35) = 34\)
\(\sum\limits_{} {d(v) = } 34 \times 55\) \( = 2\left| E \right| \Rightarrow \left| E \right|\) \( = \frac{{34 \times 35}}{2} = 595\) poignées de mains
En analyse combinatoire, on ferait \(C_{35}^2 = \frac{{35!}}{{2!33!}}\) \( = 595\)
2. Déterminons :
Graphe (1)
• La valence de chaque sommet : \(d(1) = ... = \) \(d(6) = 3\)
• La séquence de degré des graphes : 3-3-3-3-3-3
Le nombre de sommets de degré impair est pair
Graphe (2)
• La valence de chaque sommet : \(d(A) = ...\) \( = d(F) = 5\)
• La séquence de degré des graphes : 5-5-5-5-5-5
Graphe (3)
• La valence de chaque sommet :
\(d(A) = d(C)\) \( = d(D) = 2\)
\(d(B) = \) \(d(E) = 4\)
• La séquence de degré des graphes 4-4-2-2-2-2

Correction exercice IV

Une suite décroissante d’entiers naturels est dite graphique s’il existe un graphe ayant cette suite pour séquence de degré. Il suffit donc de vérifier s’il est possible de construire un graphe avec cette suite.
1. Pour cela on utilise la conséquence du lemme des poignées de mains et sa conséquence
(a) \(\sum\limits_{v \in V(G)} {{d_G}(v)} = \) \(6 + 5 + 4 + 3 + 2\) \( + 1 + 0 = 21\)
\(\left| E \right| = 10,5\)
En plus : « 5-3-1 » Le nombre de sommets de degré impair n’est pas pair.
La suite n’est graphique
(b) \(\sum\limits_{v \in V(G)} {{d_G}(v)} = 2\) \( + 2 + 2 + 2 + 2\) \( + 2 = 12\)
\(\left| E \right| = \frac{{12}}{2} = 6\)
La suite est graphique
(c) La suite n’est graphique
(d) La suite est graphique
2. Dans chacun des cas suivants dites s’il est possible de construire un graphe et construisez-le le cas échéant.
(a) Possible
(b) Pas possible
(c) Possible