Graphes planaires

On dit qu'un graphe est planaire si on peut le dessiner dans le plan de sorte que ses arêtes ne se croisent pas. Rappelons que les arêtes ne sont pas forcément rectilignes. Une carte, ou graphe planaire topologique, est une représentation particulière d'un multigraphe planaire fini. On dit qu'une carte est connexe si son graphe l'est. Une carte divise le plan en plusieurs régions. Par exemple, la carte ci-contre, avec six sommets et neuf arêtes, divise le plan en cinq régions (A, B, C, D, E). On remarque que quatre régions sont limitées alors que la cinquième (E), extérieure au diagramme, ne l'est pas. Le degré d'une région r, noté d(r), est la longueur du cycle ou de la chaîne fermée qui limite r. Dans le graphe ci-contre, d(A)=4, d(B)=3, d(C)=3, d(D)=5, d(E)=3.

On remarque que toute arête limite deux régions, ou est contenue dans une région et est alors comptée deux fois dans la chaîne fermée. Nous avons donc un lemme pour les régions, analogue au lemme des poignées de mains pour les sommets.

Lemme La somme des degrés des régions d'une carte connexe est égale à deux fois le nombre d'arêtes.

On peut vérifier ce lemme sur le graphe ci-dessus: il comporte 9 arêtes et la somme des degrés des régions vaut 18.

Théorème 3 (Euler) Euler a établi une formule qui relie le nombre de sommets S, le nombre d'arêtes A et le nombre de régions R d'une carte connexe. S - A + R = 2

Pendant de nombreuses années, les mathématiciens ont tenté de caractériser les graphes planaires. Ce problème a été résolu en 1930 par le mathématicien polonais K. Kuratowski. La démonstration du théorème sort du cadre de ce cours.

Théorème 4 (Kuratowski) Un graphe est non planaire si et seulement si il contient un sous-graphe homéomorphe à K3,3 ou K5.

K3,3		K5

Exercices

Exercice 1

Démontrez le théorème d'Euler.
Indication: Procédez par induction.

Exercice 2

Utilisez le théorème d'Euler pour démontrer que le graphe K_3,3 n'est pas planaire.

Didier Müller, 6.2.03