C - Le théorème de Kuratowski

Le théorème de Kuratowski que nous allons simplement énoncer ci-dessous prouve que, d'une certaine manière, les graphes K_3,3 et K₅ définis au paragraphe précédent, sont les ''seuls'' graphes non-planaires, au sens où l'on en trouve une ''copie'' dans n'importe quel graphe non planaire. Pour donner un sens précis à cette formulation intuitive, nous avons besoin de deux définitions.

Définition - Deux graphes G et G' sont dits homéomorphes s'ils peuvent tous deux être obtenus à partir d'un même graphe G₀ par insertion de sommets de degré 2 à l'intérieur de ses arêtes.

En d'autres termes, si on dessine chacun des graphes G et G' et si, chaque fois qu'un sommet n'est incident qu'à deux arêtes (une arrivée et un départ), on efface ce sommet en décidant qu'il n'y a plus qu'une arête, on aboutira au même graphe épuré (qui pourrait d'ailleurs ne pas coïncider avec G₀ si ce dernier contient lui aussi des sommets ``effaçables''). Remarquons que le graphe épuré est planaire si et seulement si les graphes originels le sont. En particulier, si G et G' sont homéomorphes et si l'un est planaire, l'autre l'est aussi.

Définition - Si G et G' sont deux graphes, on dit que G est une contraction de G' si on peut passer de G' à G par une suite de contractions élémentaires. On appelle ainsi l'opération consistant à choisir une arête (ab), à la supprimer en identifiant a et b à un nouveau sommet c, et à faire aboutir à c les arêtes du graphe de départ qui aboutissaient en a ou en b.

Exemple -  le graphe K₅ est une contraction du graphe de Petersen (on supprime les cinq arêtes qui relient le pentagone intérieur au pentagone extérieur).

Théorème de Kuratowski - (a) Un graphe G est planaire si et seulement si il ne contient aucun sous-graphe homéomorphe à K_3,3 ou à K₅.
(b) Un graphe G est planaire si et seulement si il ne contient aucun sous-graphe que l'on puisse contracter sur K_3,3 ou K₅.