Exercice I

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 II

1. Est-il possible de tracer les figures suivantes sans lever le crayon (et sans passer deux fois sur le même trait !…) ? Pourquoi ?
2. Soit G un graphe non eulérien. Est-il toujours possible de rendre G eulérien en lui rajoutant un sommet et quelques arêtes ?
3. Un groupe de 9 élèves se réunit chaque jour autour d’une table ronde. Combien de jours peuvent-ils se réunir si l’on souhaite que personne n’ait deux fois le même voisin ?