GRAPHES THÉORIE DES

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 K_3,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 K_3,3 ni K₅ 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 à K_3,3 ou à K₅.

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.

Nous avons vu que K₅, encore appelé graphe complet à cinq sommets, n'est pas planaire, c'est-à-dire n'admet pas de « bonne » représentation sur le plan, dans laquelle les images des arêtes ne se couperaient pas. On voit en revanche que sur un tore, et plus généralement sur une surface de genre au moins égal à 1 (c'est-à-dire, comme le tore, « percée d'au moins un trou » ; cf. fonctions analytiques - représentation conforme ; topologie - Topologie algébrique), on peut trouver facilement de telles représentations de K₅. Plus généralement, appelons K_n le graphe à n sommets dont tous les couples de sommets sont joints par une arête.

La conjecture posée par P. J. Heawood à la fin du xix^e siècle consistait à dire que le genre minimal d'une surface sur laquelle on peut trouver une « bonne » représentation de K_n est égal au plus petit entier immédiatement supérieur à :

Cette conjecture a été démontrée d'année en année pour chaque cas particulier de n modulo 12 en commençant par les plus simples, mais sa preuve complète n'a été obtenue qu'en 1969 par T. Youngs et G. Ringel. Il faut un petit livre pour contenir cette démonstration, et, si l'énoncé du résultat n'est guère sophistiqué, il faut pour l'obtenir avoir recours à des secteurs très formalisés des mathématiques.