Cet article s’intéresse aux graphes dont les représentations dans le plan ne montrent pas de croisement d’arêtes en dehors de leurs sommets. Il s’intéresse aussi à la relation existant, dans ces graphes, entre le nombre de leurs sommets, le nombre de leurs arêtes et le nombre de régions que ces arêtes déterminent dans le plan. Il s’agit de la formule d’Euler pour les graphes planaires.
Le vocabulaire de base de la théorie des graphes est développé dans Graphes 1 et la notion d’arbre en théorie des graphes est expliqué dans Graphes 2.
La rubrique s’adresse à tous ceux, petits et grands, qui souhaitent s’amuser tout en faisant des mathématiques, autour de thèmes parfois oubliés des programmes scolaires. Les connaissances utiles sont celles d’un élève de collège ou de lycée. Le cœur de cette rubrique est formé d’une petite série de thèmes choisis, dont chacun se parcourt travers un déroulé de problèmes.
Dans chaque article, certains problèmes sont accompagnés de solutions. Les solutions des autres problèmes seront mises en ligne deux semaines après la publication de l’article.
Les lecteurs sont invités à nous proposer leurs solutions des « Problèmes à résoudre par vous-mêmes ». Les solutions peuvent être rédigées comme commentaires sur l’article.
Le professeur Euler retrouve ses étudiants martiens pour la troisième fois (une première fois ici, une deuxième là). Son objectif est de leur présenter une formule que l’on attribue à son fameux aïeul Leonhard Euler, la formule d’Euler, que Descartes avait approchée avant lui. Cette formule concerne un certain type de graphes que l’on dit planaires.
Le professeur Euler revient tout d’abord sur quelques notions qu’il a développées lors de ses deux premières leçons. Il rappelle rapidement qu’un graphe est complètement défini par la donnée de ses sommets et de ses arêtes (voir article Graphe 1) et il insiste particulièrement sur un type de graphe qui porte le nom « d’arbre » (voir article Graphe 2), dont il rappelle la définition :
Un arbre est un graphe connexe qui n’a pas de cycle.
Il en dessine un exemple au tableau.
Le professeur Euler en profite alors pour rappeler qu’un graphe connexe est un graphe dans lequel, pour chaque paire de sommets, il existe un chemin qui les relie (concrètement, il s’agit d’un graphe en « un seul morceau ») et qu’un cycle, dans un graphe, est un chemin élémentaire dont le début coïncide avec la fin (concrètement, il s’agit d’une « boucle »).
Il rappelle aussi une définition équivalente d’un arbre :
Un arbre est un graphe dans lequel deux sommets quelconques sont reliés par un et un seul chemin.
Il rappelle enfin que, dans tout arbre ayant au moins deux sommets, il existe toujours un sommet d’où part une seule arête (un tel sommet est dit « suspendu » et cette arête est dite « extrémale »).
Afin que cette notion d’arbre soit bien ancrée dans l’esprit de ses étudiants, le professeur Euler leur propose de résoudre le problème suivant.
Problème 1. Le réseau informatique
Le parc informatique d’une école est constitué de cinquante ordinateurs. Un informaticien veut les mettre en réseau de telle sorte que, entre deux quelconques de ces ordinateurs, il n’y ait qu’un seul chemin de câbles qui les relie. Combien de câbles l’informaticien devra-t-il utiliser pour construire ce réseau ?
SOLUTION (À LIRE AVANT DE POURSUIVRE LA LECTURE DE L’ARTICLE)
Il est clair que le réseau informatique de cette école peut être représenté par un graphe dont les sommets sont les ordinateurs et dont les arêtes sont les câbles qui les relient. Il est clair aussi que ce graphe est un arbre.
Cet arbre possède au moins un sommet suspendu. Enlevons un sommet suspendu ainsi que l’arête extrémale qui part de ce sommet. Le nouveau graphe est aussi un arbre. Cet arbre possède à son tour au moins un sommet suspendu. Enlevons encore un fois un sommet suspendu avec l’arête qui part de ce sommet. Si on répète 49 fois cette opération, on obtient un graphe avec un seul sommet (et bien sûr sans arête). Puisqu’à chaque fois on a enlevé exactement une arête, le graphe initial possédait 49 arêtes. L’informaticien devra donc utiliser 49 câbles pour mettre ses 50 ordinateurs en réseau.
Une généralisation de ce problème permet aisément au professeur Euler d’énoncer le théorème suivant dans lequel apparait la relation entre le nombre de sommets et le nombre d’arêtes, dans un arbre.
Le nombre d’arêtes dans un arbre est égal au nombre de ses sommets diminué de 1.
Le décor étant maintenant planté, le professeur Euler aborde le sujet de sa leçon d’aujourd’hui. Il dessine sur son tableau les quatre graphes connexes ci-dessous et demande à ses étudiants de les commenter, en soulignant ce qui les rassemble ou ce qui les distingue.
Dessin 1
Un premier étudiant prend la parole et remarque que, dans le second graphe, il y a une arête de plus que dans le premier. Il remarque aussi que, dans le graphe 2, cette arête supplémentaire en coupe une autre, ailleurs qu’en l’un des sommets du graphe. Il remarque enfin que, dans le graphe 1, il n’y a aucun croisement de ce type.
Le professeur Euler acquiesce et demande alors à une étudiante du premier rang de commenter les graphes 2 et 3. Cette étudiante souligne tout d’abord que ces deux graphes ont le même nombre de sommets et le même nombre d’arêtes. Elle ajoute que ces deux graphes sont exactement structurés de la même manière ; plus précisément qu’il existe une bijection \(f\) entre les sommets du graphe 2 et ceux du graphe 3 telle que deux sommets {A} et {B} du graphe 1 sont reliés par une arête si et seulement si les sommets \(f(A)\) et \(f(B)\) du graphe 3 sont aussi reliés par une arête (on dit des graphes 2 et 3 qu’ils sont isomorphes).
Le professeur Euler applaudit cette remarque fort judicieuse et demande si, cependant, quelque chose distingue les graphes 2 et 3. « Oui» répond immédiatement l’étudiante, « Le graphe 3 ne montre pas d’arêtes se croisant en dehors de ses sommets ».
« Parfait » dit le Professeur Euler. Pour résumer ce qui vient d’être dit, il existe des graphes dont la représentation dans le plan ne présente pas de croisement d’arêtes en dehors des sommets (les graphes 1 et 3) ; il en existe aussi qui sont isomorphes à des graphes dont la représentation dans le plan ne présente pas de croisement d’arêtes en dehors des sommets (graphe 2 isomorphe au graphe 3). De tous ces graphes, on dit qu’ils sont planaires. Le professeur Euler note alors les définitions suivantes sur son tableau.
Un graphe planaire est un graphe qui peut être dessiné dans un plan de telle manière que ses arêtes ne se coupent pas en dehors de leurs extrémités. Lorsqu’un graphe planaire est dessiné de telle manière que ses arêtes ne se coupent pas en dehors de leurs extrémités, on dit qu’il est représenté sans croisement.
C’est tout naturellement qu’une main se lève dans l’amphithéâtre et qu’un étudiant demande si le graphe 4 est planaire. Le Professeur Euler lui répond que la leçon qu’il va maintenant leur présenter permettra de se convaincre que ce graphe n’est pas planaire mais, pour l’instant, la réponse est prématurée.
Tout est maintenant en place pour aborder la fameuse formule d’Euler. C’est une formule qui, à l’origine, concernait les polyèdres convexes, mais que le professeur Euler va formuler dans le cadre des graphes connexes planaires représentés sans croisement.
Pour introduire cette formule, le professeur Euler reprend le graphe 3 présenté au début de la leçon. Ce graphe est un graphe planaire connexe, dessiné sans croisement.
Il fait remarquer que ce graphe partage le plan en régions et que ces régions sont au nombre de 4 (ne pas oublier la région extérieure au tracé du graphe).
Le professeur Euler précise alors que la formule qu’il veut établir exprime, dans un graphe planaire connexe représenté sans croisement, une relation entre le nombre \(A\) de ses arêtes, le nombre \(S\) de ses sommets et le nombre \(R\) des régions qu’il détermine. Afin de conjecturer cette formule, le professeur demande à chacun de ses étudiants de représenter un graphe connexe planaire, sans croisement d’arêtes, et d’y associer les trois nombres
\(R\), \(A\) et \(S\). Voici quelques réponses apportées par les étudiants.
Dessin 2
Une formule paraît se dégager. Tous les cas de figures représentés ci-dessus vérifient la relation
\[R – A + S = 2.\]
Et le professeur Euler énonce le théorème qu’il souhaite maintenant établir.
Pour un graphe connexe et planaire dessiné sans croisement, on a l’égalité \(R – A + S = 2\), où \(R\) désigne le nombre de régions déterminées par le graphe dans le plan, \(S\) le nombre des sommets du graphe et \(A\) le nombre de ses arêtes.
Pour faire la démonstration, le Professeur Euler considère un graphe connexe planaire quelconque, dans sa représentation sans croisement. Ce graphe possède \(A\) arêtes, \(S\) sommets et il détermine \(R\) régions dans le plan. Il propose alors à ses étudiants d’enlever une à une les arêtes de ce graphe, en faisant attention à chaque fois à ne pas détruire la connexité du graphe. Remarquons que si un graphe connexe possède un cycle, on peut toujours enlever une arête arbitraire de ce cycle sans détruire la connexité du graphe. Ceci signifie que, lorsqu’on ne pourra plus enlever d’arête, on aura un arbre.
Étudions maintenant de quelle manière évolue chacun des trois nombres \(R\), \(A\) et \(S\) au cours des suppressions successives d’arêtes. Le Professeur Euler explique que, à chaque suppression d’arête, le nombre de sommets ne change pas, le nombre d’arêtes diminue de 1 et le nombre de régions diminue aussi de 1, puisque les deux anciennes régions voisines de cette arête forment alors une seule région.
Une main se lève alors dans l’amphithéâtre et un étudiant exprime sa perplexité quant à l’évolution du nombre \(R\). Est-on sûr que le nombre de régions baisse d’une unité à chaque fois qu’on supprime une arête ? Le Professeur Euler promet à cet étudiant de revenir sur cette question à la fin de la démonstration et poursuit son raisonnement.
Quand on enlève les arêtes du graphe une par une, en préservant la connexité du graphe, le nombre \(R – A + S\) ne change pas. Lorsque notre graphe devient un arbre, on a \(S – A = 1\) comme démontré dans le problème 1 et le nombre de régions qu’il détermine est \(R = 1\). En effet si \(R\) était supérieur ou égal à 2, l’une de ces régions serait close par des arêtes qui constitueraient un cycle pour ce graphe. Ceci n’est pas possible dans un arbre. Donc, pour l’arbre obtenu, \(R – A + S =R+(S-A)= 2\). Par conséquent, l’égalité \(R – A + S = 2\) est vraie aussi pour le graphe initial.
Le Professeur Euler se retourne alors vers l’étudiant qu’un point de la démonstration a laissé perplexe et lui demande de s’exprimer sur ce qui le fait douter.
“Ce qui me dérange, c’est que, lorsque dans un graphe planaire représenté sans croisement, on supprime une arête dont les deux côtés appartiennent à la même région, le nombre de régions ne baisse pas d’une unité !”
Pour illustrer son propos, l’étudiant se déplace vers le tableau et propose le graphe ci-dessous.
Dessin 3
Dans ce graphe, en effet, la suppression de l’arête \(AB\) ne diminue pas le nombre de régions.
Le Professeur rassure alors son étudiant en lui disant qu’il ne peut, dans ce cas de figure, comme dans un cas plus général d’arêtes dont les deux côtés appartiennent à la même région, supprimer ces arêtes sans détruire la connexité du graphe. En effet, si les deux côtés d’une arête sont dans la même région, on peut tracer une ligne pointillée dans cette région, qui part d’un côté de l’arête AB et revient de l’autre côté
Si on découpe suivant cette ligne pointillée on obtient deux composantes connexes du graphe privé de l’arête AB : l’une contient le sommet A et l’autre le sommet B. On n’avait donc pas le droit d’enlever l’arête AB.
La formule d’Euler est donc démontrée.
Problème 2. Pas toujours facile de voyager
Sur une planète, il y a 10 villes, certaines villes étant reliées par des lignes de chemin de fer. Il n’y a pas de correspondances en dehors des villes, et aucun chemin de fer ne passe sous un autre. Il y a 18 chemins de fer sur la planète, et ils divisent la planète en 11 parcs. Montrez que, sur cette planète, on peut trouver deux villes entre lesquelles il n’existe aucune liaison ferroviaire (même en passant par d’autre(s) ville(s)).
Solution
Considérons le graphe dont les sommets sont les villes de cette planète et dont les arêtes sont chacun des chemins de fer joignant deux à deux certaines de ces villes. Les données du problème permettent de dire que ce graphe possède 10 sommets, 18 arêtes et qu’il détermine 11 régions sur la planète. De plus, ce graphe est planaire et représenté sans croisement car l’énoncé précise qu’aucun chemin de fer ne passe sous un autre et qu’aucune correspondance n’est possible en dehors des villes. Remarquons que ce graphe ne vérifie pas la formule \(R-A+S=2\) ; en effet : 11-18+10 =3. Ce graphe n’est donc pas connexe. Parmi les 10 villes de la planète, il en existe donc au moins deux entre lesquelles il n’existe aucune liaison ferroviaire, même en passant par d’autre(s) ville(s).
Problème 3. Michel, le jardinier, triangule
Michel le jardinier possède un petit carré de jardin qu’il souhaite partager en triangles. Il plante 12 piquets à l’intérieur de ce carré et 4 autres aux quatre coins du jardin, de telle manière que trois quelconques de ces 16 piquets ne soient jamais alignés. Ensuite, il relie tous les piquets entre eux par des cordeaux de telle façon que ces cordeaux ne se croisent jamais, et que le carré de Michel, délimité sur ses quatre côtés par des cordeaux, soit partagé en plusieurs petits triangles. Michel a aussi appliqué la règle suivante : deux quelconques des piquets sont toujours reliés par une succession de cordeaux.
Dessin 4
Le nombre de petits triangles obtenus dépend-il de la disposition des piquets ?
Solution
Associons un graphe au découpage en triangles effectué par Michel dans son carré de jardin. Les sommets de ce graphe sont les 16 piquets et les arêtes les cordeaux tendus entre ces piquets. Ce graphe est connexe. Comme les cordeaux ne se croisent pas, ce graphe est aussi planaire. Remarquons que les régions déterminées par ce graphe planaire, représenté sans croisement, sont toutes des triangles sauf celle qui correspond à l’extérieur du carré de jardin. Chacune des régions triangulaires est délimitée par 3 arêtes ; la région extérieure est délimitée par 4 arêtes. Puisque chacune des arêtes délimite deux régions, nous avons la relation \(3(R – 1) + 4 = 2 A \) , où \(A\) désigne le nombre d’arêtes du graphe et où \(R\) désigne le nombre des régions que sa représentation sans croisement détermine dans le plan. Nous avons donc l’égalité \(A = \displaystyle\frac{3R+1}{2}\). Pour ce graphe planaire et connexe possédant 16 sommets, la formule d’Euler s’applique et donne l’égalité \(R – \displaystyle\frac{3R+1}{2} + 16 = 2\). D’où \(R = 27\). Michel a donc nécessairement partagé son carré de jardin en 26 triangles.
Remarquer qu’ici, pour résoudre ce problème, nous avons procédé à des dénombrements comme nous l’avions déjà beaucoup fait dans Graphes 1 et Graphes 2.
Problème 4. Une inégalité pour graphe planaire
Montrer que, pour un graphe planaire ayant au moins deux arêtes et dessiné sans croisement, on a l’inégalité \(2A \ge 3R\) .
Solution
Deux cas de figure peuvent se présenter : soit le graphe possède exactement deux arêtes, soit il en possède au moins 3.
Dans le cas où le graphe n’a que deux arêtes, celles-ci ne déterminent qu’une seule région et l’inégalité \(2A \ge 3R\) est vérifiée.
Si le graphe possède au moins trois arêtes, comptons pour chacune des régions le nombre d’arêtes qui l’entourent et additionnons tous les nombres obtenus. Notons ce résultat \(\Sigma\). Chacune des régions étant entourée par au moins 3 arêtes, on a l’inégalité \(\Sigma \ge 3R\). Par ailleurs, chaque arête sépare au plus deux régions. On a donc l’inégalité \(2A \ge \Sigma\). Par conséquent, \(2A \ge 3R\).
Problème 5. Une inégalité pour graphe planaire connexe
Montrer que pour tout graphe planaire connexe ayant au moins deux arêtes, on a l’inégalité \( A \le 3S – 6\) .
Solution
En partant de la formule d’Euler : \(R – A + S = 2\) et en appliquant l’inégalité démontrée dans le problème précédent, \(R \le \displaystyle\frac{2A}{3}\) ,on obtient :
\(\displaystyle\frac{2A}{3} – A + S \ge 2\)
Par conséquent : \(A \le 3S – 6\).
Le Professeur Euler fait remarquer alors à ses étudiants qu’après avoir résolu ce problème, ils ont maintenant les moyens de démontrer que le graphe 4 du dessin 1, qu’il redessine maintenant au tableau, n’est pas un graphe planaire :
En effet, pour ce graphe connexe, on a \(S=5\) et \(A=10\). L’inégalité \(A \le 3S – 6\) n’est pas vérifiée. Ce graphe n’est donc pas planaire.
Problème 6. Les trois petits cochons
Les trois petits cochons habitent dans trois maisons voisines qui doivent être raccordées séparément au réseau électrique, à celui du gaz et à celui de l’eau. C’est un vrai casse-tête pour les trois compagnies à qui il est interdit de « croiser » leurs différentes tranchées.
Dessin 5
Pensez-vous que les trois compagnies pourront creuser chacune leurs trois tranchées sans qu’elles ne se « croisent » ?
Solution
Il s’agit de savoir si le graphe représenté ici sur le dessin 11 est un graphe planaire.
Dessin 11
Si ce graphe est planaire, une représentation sans croisement en est possible et les trois compagnies pourront creuser leurs tranchées sans qu’elles ne se croisent. Si ce graphe n’est pas planaire, le « décroisement » des tranchées ne sera pas possible.
Supposons que ce graphe soit planaire et imaginons qu’il soit dessiné sans croisement. Pour ce graphe nous avons S = 6 et A = 9. D’après la formule d’Euler, nous avons donc R = 5, c’est-à-dire que le graphe « décroisé » détermine 5 régions dans le plan. Chacune de ces régions est délimitée par au moins 4 arêtes ; en effet, ce graphe ne possède aucun cycle de longueur 2 (par définition), ni de cycle de longueur 3, car il n’a pas d’arêtes entre deux maisons ou entre deux points de distribution. Chaque arête bordant deux régions, on a \(4R \le 2A\). On a donc \(4 \times 5 \le 2 \times 9\) , ce qui est absurde. Le graphe du dessin 11 n’est donc pas un graphe planaire. Le problème est donc insoluble pour les trois compagnies !
On connaît maintenant plusieurs graphes non planaires, par exemple, le graphe complet à 5 sommets (le graphe 4 du dessin 1) et le graphe du problème 6. À partir de ces graphes, on peut construire de nouveaux graphes non planaires.
Une expansion (on dit aussi subdivision) d’un graphe est le résultat de l’ajout d’un ou plusieurs sommets sur une ou plusieurs arêtes (par exemple, transformation de l’arête •—-• en •—•—•). Une expansion d’un graphe non planaire n’est pas planaire non plus.
Dans un graphe, on peut enlever certaines arêtes et certains sommets (en enlevant un sommet, on enlève aussi toutes les arêtes partant de ce sommet). Le résultat d’une telle procédure s’appelle un sous-graphe. Si un graphe contient un sous-graphe qui n’est pas planaire, le graphe lui-même n’est pas planaire.
On obtient que tout graphe contenant comme sous-graphe une expansion du graphe complet à 5 sommets ou du graphe du problème 6 n’est pas planaire. De façon remarquable, l’énoncé réciproque est aussi vrai. Cette caractérisation des graphes planaires est donnée par le théorème suivant de Kuratowski :
Un graphe est planaire si et seulement s’il ne contient pas de sous-graphe qui est une expansion du graphe complet à 5 sommets ou du graphe du problème 6.
Le professeur Euler prend congé de ses étudiants sans oublier de leur soumettre quelques problèmes à résoudre par eux-mêmes …
Problème 7. Pas plus que 5
Montrer que tout graphe planaire possède au moins un sommet à partir duquel partent au plus 5 arêtes.
Solution
Il est suffisant de montrer l’énoncé pour un graphe connexe. Supposons qu’il existe un graphe planaire connexe tel que de chaque sommet de ce graphe partent au moins 6 arêtes. Donc, pour ce graphe, on a l’inégalité \(6S \le 2A\), c’est-à-dire, \(3S \le A\). D’autre part, ce graphe a au moins deux arêtes. Donc, d’après le résultat du problème 5, on a l’inégalité \( A \le 3S – 6\). On obtient
\[3S \le A \le 3S – 6.\]
Contradiction.
Problème 8. Le graphe complet à 11 sommets
On considère le graphe complet à 11 sommets et on colorie ses arêtes en deux couleurs différentes, les unes en bleu, les autres en rouge. Les arêtes bleues et leurs extrémités constituent un premier sous-graphe. Les arêtes rouges et leurs extrémités constituent un deuxième sous-graphe. Montrer qu’au moins un de ces deux sous-graphes n’est pas planaire.
Dessin 6
Solution
Le graphe complet à 11 sommets possède 11 x 10/2 arêtes, soit 55 arêtes. En coloriant chacune de ces arêtes en bleu ou en rouge, on obtient deux sous-graphes ayant chacun au maximum 11 sommets et dont l’un des deux possède au moins 28 arêtes (puisque la somme des nombres d’arêtes des deux graphes vaut 55). Mais \(28>3 \times 11 -6\). Donc ce sous-graphe n’est pas planaire.
Problème 9. Pas plus de cinq couleurs pour colorier une carte de géographie
On considère une carte de géographie de format rectangulaire constituée de régions séparés par des frontières (par exemple, la carte des régions de France métropolitaine et continentale). On suppose que chaque région est d’un seul tenant et qu’il n’y a pas deux régions se « touchant » par seulement un coin. Pour colorier cette carte, nous allons utiliser une couleur par région de sorte que deux régions frontalières soient bien sûr coloriées de couleurs différentes.
On souhaite utiliser le plus petit nombre de couleurs différentes.
Montrer que cinq couleurs différentes suffisent pour colorier n’importe quelle carte de géographie respectant les conditions décrites précédemment.
Solution
Nous allons associer à notre carte de géographie, un graphe, de la manière suivante:
Chaque région de la carte à colorier sera un sommet du graphe, et à chaque fois que deux régions de la carte ont un frontière commune, les deux sommets correspondant du graphe seront reliés par un arête.
Par construction, le graphe ainsi formé est un graphe planaire.
Colorier la carte revient à colorier les sommets du graphe de sorte que deux sommmets adjacents (c’est-à-dire reliés par une arête) soient toujours de couleurs différentes.
Nous allons démontrer que cinq couleurs suffisent (on dira que le graphe est “5-coloriable”). On note v le nombre de sommets du graphe.
Lorsque v<=5, évidemment, cinq couleurs suffisent.
Lorsque v=6, si tous les sommets étaient joints par une arête, il y aurait, en tout, 15 arêtes et 24 régions (faire un dessin et ne pas oublier la région “extérieure”) mais ceci contredit la formule d’Euler puisque 6+24-15 est différent de 2. Par conséquent, au moins deux sommets ne sont pas joints par une arête. On peut colorier ces deux sommets avec la même couleur, les quatre couleurs restantes pouvant être utiliser pour colorier les quatre autres sommets.
Lorsque v>=6, raisonnons par récurrence sur v.
Soit n un entier supérieur ou égal à 6.
Supposons que tout graphe planaire ayant n sommets soit 5-coloriable.
Considérons un graphe planaire G ayant (n+1) sommets.
D’après le problème 7, G possède un sommet de dégré au plus 5. Notons A un tel sommet.
On enlève de G le sommet A et toutes les arêtes qui lui sont incidentes: le graphe G – {A} résultant est, par hypothèse de réurrence, 5-coloriable.
Si au moins deux des cinq voisins de A sont de la même couleur que A, il reste une couleur libre pour colorier A.
Sinon, c’est-à-dire si les cinq voisins de A sont coloriés avec cinq couleurs différentes, nous allons voir qu’il est encore possible de libérer une couleur pour A. Voyons comment procéder. Tournons autour de A et appelons B, C, D, E, F les voisins de A dans l’ordre d’apparition. Notons b la couleur de B, c celle de C, etc.
Distinguons deux cas.
(i) S’il n’existe pas de suite de sommets deux à deux reliés par une arête, partant de B, arrivant en D, coloriés (alternativement) avec les couleurs b et d, on peut colorier B avec d puis de proche en proche, permuter les couleurs b et d. Ainsi les voisins de A sont coloriés avec quatre couleurs (B et D avec b, C avec c, E avec e et F avec f); on peut donc colorier A avec d.
(ii) S’il existe une suite, partant de B et aboutissant en D, de sommets successifs coloriés avec b et d alors il ne peut pas exister une suite, partant de C et aboutissant en E, de sommets coloriés avec c et e; expliquons pourquoi.
Si ces deux suites cohabitaient, elles auraient (au moins) un sommet en commun – puisque le graphe est planaire donc sans croisement d’arêtes – qui serait dessiné avec, à la fois, une des couleurs b ou d et avec une des couleurs c et e: ceci n’est pas possible !
On peut donc effectuer la même opération que dans le cas précédent avec les sommets C et E à la place des sommets B et D. On libère ainsi la couleur e qui est alors disponible pour A.
Conclusion:
On peut toujours colorier une carte de géographie avec cinq couleurs sans que deux régions voisines n’aient la même couleur.
Il est possible d’utiliser des commandes LaTeX pour rédiger des commentaires — mais nous ne recommandons pas d’en abuser ! Les formules mathématiques doivent être composées avec les balises .
Par exemple, on pourra écrire que sont les deux solutions complexes de l’équation .
Si vous souhaitez ajouter une figure ou déposer un fichier ou pour toute autre question, merci de vous adresser au secrétariat.