2. Théorèmes de Kuratowski et de Youngs-Ringel
Commençons par un problème de topologie du plan que la théorie des graphes a transformé en problème combinatoire.
Un jeu connu des journaux enfantins consiste à tenter de faire tracer des chemins partant de trois maisons et allant vers trois puits... sans que ces chemins se coupent. Le problème est sans solution. On dit que le graphe K3,3 n'est pas planaire. Plus généralement, un graphe est planaire s'il en existe une représentation géométrique dans le plan (ou sur une surface quelconque de genre 0) telle que les représentations des arêtes ne se coupent pas. La planarité peut donc passer pour une question de géométrie différentielle, puisqu'il s'agit de tracer des courbes continues sur des surfaces. Pourtant, Kuratowski a montré que cette question pouvait être considérée comme purement combinatoire.
Le Polonais Kuratowski a commencé par montrer (1930) que ni K3,3 ni K5 ne sont planaires. Posons deux définitions préliminaires. On dit qu'un graphe G contient un graphe G′, ou que G′ est induit dans G, si l'on peut obtenir G′ à partir de G en effaçant des sommets et des arêtes de G. On dit que l'on peut contracter G en un graphe G′, ou que G′ est une contraction de G, si, en supprimant tous les sommets de G auxquels n'arrivent que deux arêtes et en remplaçant ces deux arêtes et le sommet en question par une simple arête, on obtient G′.
Théorème de Kuratowski : Pour qu'un graphe G soit planaire, il faut et il suffit qu'il ne contienne aucun graphe G′ qui puisse être rendu par contraction identique à K3,3 ou à K5.
La question de la planarité des graphes, ou plus généralement de leur représentation géométrique sur des surfaces, est un thème récurrent en théorie des graphes au sens où, de congrès en congrès, de nombreuses conjectures nouvelles sont proposées et de très anciennes résolues, parfois au pris d'efforts considérables. C'est ce qui est arrivé en 1969 à la conjecture de P. J. Heawood.
Nou […]
… pour nos abonnés, l'article se prolonge sur 5 pages…
