| RÉPONSE À LA DEUXIÈME QUESTION :
(cette configuration à 4 couples de maisons est le K2,2,2,2)
On veut prouver qu'il est impossible de relier chaque maison à toutes les maisons de couleur différente sans croiser les lignes.
C'est-à-dire qu'on veut montrer que le graphe est non planaire. On va donc utiliser la caractérisation des graphes planaires par Kuratowski :
"Un graphe n'est pas planaire si et seulement si on peut en extraire un K5 ou un K3,3.
Sur ce dessin, le K5 à gauche et le K3,3 à droite :
Ni le K5 ni le K3,3 ne sont dessinables sans croisements ! Donc si le K2,2,2,2 contient l'un ou l'autre, on ne peut pas le dessiner sans croisements.
On va donc chercher un K5 ou un K3,3 dissimulé dans le K2,2,2,2 pour prouver qu'il n'est pas dessinable.
1) Y a-t-il un K5 dans le K2,2,2,2 ?
Voici le K2,2,2,2 :
(chaque point est relié à tous les autres, sauf à celui de même couleur)
Le K5 est un ensemble de 5 points tous reliés les uns aux autres. On va donc prendre 5 points au hasard parmi les 8 points du K2,2,2,2.
Sur les 5 points choisis, au moins deux ont la même couleur (car il n'y a que 4 couleurs), or ces deux points de même couleur ne sont pas reliés (par définition du K2,2,2,2).
Donc le K2,2,2,2 ne contient pas le K5.
2) Y a-t-il un K3,3 dans le K2,2,2,2 ?
On doit choisir 6 points du K2,2,2,2. On espère que ces 6 points seront séparables en deux groupes de 3 points tel que chaque point du premier groupe est relié à chaque point du second (c'est la définition du K3,3).
Si dans le K2,2,2,2 je prends comme groupe 1 deux rouges et un bleu, et dans le groupe 2 deux verts et un jaune :
Je peux relier (en rose) chaque point du groupe 1 à chaque point du groupe 2.
Le K2,2,2,2 contient donc un K3,3.
D'après le théorème de Kuratowski, on ne peut alors pas dessiner le K2,2,2,2 sans croisements.
Conclusion : le problème des voisins n'est pas résoluble avec 8 maisons et 4 couleurs.
C'est rigolo, non ?
|