Exercice 4 - le savant fou en voyage

Un chimiste souhaite transporter les produits $A, B, C, D, E$, dans des valises. Les couples de produits suivants ne doivent en aucun cas être transportés dans la même valise :

• $A$ et $C$
• $A$ et $D$
• $C$ et $D$
• $A$ et $B$
• $B$ et $D$
• $A$ et $E$
• $E$ et $C$

Le but est de répartir les produits dans un minimum de valises.

1. Ramenez-vous à un problème classique de théorie des graphes. Dessinez le graphe.
2. Ce problème est-il NP-Complet ?
3. Proposez une solution réalisable à trois valises pour ce problème.