Bonjour,
Voici un exo tout frais extrait des Olympiades Internationales 2007 qui ont lieu en ce moment^^
Dans un concours mathématique certains concurrents sont amis. L'amitié est une relation symétrique. On appelle une clique un groupe de concurrents tel que si on prend deux personnes dans ce groupe, elles sont toujours amies (En particulier, un groupe de 0 ou 1 personne est une clique). On appelle "taille" de la clique le nombre de personnes de cette clique.
Etant donné que, dans ce concours, la taille maximale des cliques est pair, montrer que les concurrents peuvent être répartis dans deux pièces de telle sorte que la taille maximale des cliques de la première pièce soit égale à la taille maximale des cliques de la seconde pièce.