Exercice I

1. Soient les graphes suivants :
a) Lister tous ses sommets et arêtes.
b) Les différents sommets adjacents.
c) Le(s) sommet(s) isolé(s).
d) Donner son ordre.
2. Déterminez la valence de chaque sommet, l’ordre, la taille des graphes suivants :

Exercice II

Un tournoi d’échecs oppose 06 personnes. Chaque joueur doit affronter tous les autres.
1. Construisez un graphe représentant toutes les parties possibles.
2. Combien de match au total doit-on livrer ?
3. Combien de match doit-t-on livrer pour la première phase ?

Exercice III (PC etT E)

1. Démontrer le Lemme des poignées de mains
\(\sum\limits_{v \in V(G)} {{d_G}(v) = } \) \(2\left| {E(G)} \right|\)
2. En appliquant la conséquence du lemme des poignées de mains. « Dans un graphe simple G, le nombre de sommets de degré impair est pair »
Montrer dans un graphe simple G suivant, le nombre de sommets de degré impair est pair
3. Déterminer la séquence de degré du graphe ci-dessous, est-elle graphique?
4. La séquence de degré du graphe 4-3-3-2-1 est-elle graphique ?

Exercice IV

1. Dans une réunion de 5 personnes, on suppose que tout le monde salue tout le monde,
• Combien de poignées de mains ont été échangés?
• Même question pour 35 personnes.
2. Déterminez les degrés de chaque sommet et la séquence de degré des graphes suivants :

Exercice V

1. Déterminez en expliquant votre logique, lesquelles des suites suivantes sont graphiques.
(a) (6,5,4,3,2,1,0)
(b) (2,2,2,2,2,2)
(c) (5,3,3,3,3,3)
(d) (1,1,1,1,1,1)
b) Trouvez deux graphes correspondant à la suite (3, 2, 2, 2, 1).
2. Dans chacun des cas suivants dites s’il est possible de construire un graphe et construisez-le le cas échéant.
a) Les sommets ont pour degré respectif (6,5, 5, 5, 5, 4, 4)
b) Les sommets ont pour degré respectif (5, 4, 3, 3, 2)
c) Les sommets ont pour degré respectif (4, 3,2, 2, 1)