1. On place d'abord les sommets A, B, C, D, E et F qui représentent les pièces et on relie, par des arêtes, les pièces qui communiquent : A-B, A-E, A-F, B-C, C-D, C-E, D-E, E-F.

   

2. Le graphe est connexe. En effet, un graphe est connexe si deux sommets quelconques peuvent être reliés par une chaîne ce qui est le cas ici.

   Le graphe n'est pas complet. Un graphe non orienté est complet si et seulement si tous ses sommets sont reliés par une arête. Ce n'est pas le cas ici pour A et C par exemple.

   À retenir

   Un graphe est complet si et seulement si tous ses sommets sont deux à deux adjacents (c'est à dire reliés par une arête).

   Un graphe est connexe si et seulement si deux sommets quelconques peuvent être reliés par une chaîne (intuitivement cela signifie que le graphe est en « un seul morceau »).

1. On recherche s'il existe une chaîne eulérienne, c'est à dire une chaîne qui contient une fois et une seule chacune des arêtes du graphe.

   D'après le théorème d'Euler, un graphe connexe contient une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommets de degré impair.

   Le degré de chacun des sommets est donné par le tableau ci-après :

   Sommet	A	B	C	D	E	F
   Degré	3	2	3	2	4	2

   Le graphe (G) possède deux sommets de degré impair : A et C.

   Il est donc possible de parcourir l'appartement en empruntant chacune des 8 portes une fois et une seule, par exemple en suivant le trajet : A-B-C-D-E-F-A-E-C.

   À retenir

   Une chaîne eulérienne est une chaîne qui contient une fois et une seule chacune des arêtes du graphe.

   Trouver un chemin qui emprunte chaque arête une fois et une seule revient à trouver une chaîne eulérienne.

   Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommet(s) de degré impair.

2. Dans cette question, on recherche l'existence d'un cycle eulérien (un cycle est une chaîne fermée).

   Or, d'après le théorème d'Euler, un graphe connexe contient un cycle eulérien si et seulement s'il ne possède aucun sommet de degré impair.

   Ici, A et C sont de degré impair. Toute chaîne eulérienne aura pour extrémités A et C et ne sera donc pas un cycle.

   Par conséquent, il n'est pas possible de parcourir l'appartement en empruntant chaque porte une fois et une seule et en partant et en arrivant dans la même pièce.

   À retenir

   Un cycle eulérien est une chaîne fermée qui contient une fois et une seule chacune des arêtes du graphe.

   Trouver un chemin qui emprunte chaque arête une fois et une seule et dont les sommets de départ et d'arrivée sont identiques revient à trouver un cycle eulérien.

   Un graphe connexe admet un cycle eulérien si et seulement s'il ne possède aucun sommet de degré impair.

Numérotons les pièces A: 1, B: 2, C: 3, D: 4, E: 5, F: 6.
La matrice de transition $M$ associée au graphe précédent s'obtient en plaçant à la $i$-ième ligne et à la $j$-ième colonne :

• un « 1 » si les pièces numérotées $i$ et $j$ sont reliés par une arête ;

• un « 0 » sinon.

On obtient alors la matrice :

1. Le coefficient de $M^3$ situé à la $i$-ième ligne et à la $j$-ième colonne indique le nombre de chemins de trois arêtes menant du sommet numéro $i$ au sommet numéro $j$.

   Ici, le coefficient situé à la première ligne et à la quatrième colonne est 3. Il y a donc 3 chemins permettant d'aller de la pièce A à la pièce D en empruntant exactement trois portes.

   À l'aide du graphe, on trouve les chemins : A-B-C-D, A-E-C-D et A-F-E-D.

   À retenir

   Le coefficient de la matrice $M^n$ situé à la $i$-ième ligne et à la $j$-ième colonne correspond au nombre de chemins de longueur \bm{n} menant du sommet numéro $i$ au sommet numéro $j$.

2. La matrice $M^3$ comporte un unique coefficient nul situé en ligne 2 et en colonne 2. Cela signifie qu'il n'est pas possible de partir de la pièce B pour revenir à la pièce B en empruntant exactement 3 portes mais que, mis à part ce cas, il est toujours possible de joindre deux pièces en empruntant exactement 3 portes.

   Comme l'énoncé précise deux pièces différentes, il est effectivement toujours possible de joindre deux pièces différentes en empruntant exactement trois portes.

1. Considérons le sous-graphe constitué des sommets A, E et F. Chacun de ces trois sommets est relié aux deux autres, donc ce sous-graphe est complet. Le sous-graphe constitué de C, E et D est lui-aussi complet.

2. Il est possible de repeindre les pièces en respectant les consignes de l'énoncé et avec seulement trois couleurs.

   Le sous-graphe A, E et F étant complet, il faudra nécessairement trois couleurs différentes pour peindre ces trois pièces.
   Il en est de même pour les pièces C, E et D.

   En respectant ces contraintes, il est facile de trouver une solution au problème posé ; par exemple (mais il y a d'autres solutions ...) :

   Couleur 1 : E, B
   Couleur 2 : A, C
   Couleur 3 : F, D.