Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Chapitre 5 - Graphes planaires

 

B - Identité d'Euler. Exemples de graphes non planaires

Soit G un graphe planaire. Sa représentation dans le plan détermine des régions, bordées par des arêtes et à l'intérieur desquelles il est toujours possible d'aller d'un point à un autre sans couper d'arête (on peut imaginer les arêtes comme des lignes frontières : les régions en question seraient alors les divers pays délimités par ces frontières). On appelle ces régions des faces. Il faut noter que l'une des faces entoure complètement le graphe (on l'appelle la face non bornée du plongement). Il n'est pas évident a priori que si l'on plonge de deux manières différentes G dans le plan, le nombre de faces dans les deux figures soit le même. C'est pourtant le cas, comme le prouve l'identité d'Euler, qui permet en outre de déterminer le nombre de faces en fonction des nombres de sommets et d'arêtes du graphe.

Théorème - (Identité d'Euler) Si S (resp. A) désigne le nombre de sommets (resp. d'arêtes) d'un graphe planaire connexe G, si F désigne le nombre de faces (y compris la face non bornée) d'un plongement de G dans le plan,

Démonstration - On raisonne par récurrence sur le nombre A d'arêtes. Si A = 1, le graphe G possède soit 1 sommet, soit 2. Dans le premier cas, l'arête est une boucle, le plongement de G dans le plan détermine deux faces (l'intérieur et l'extérieur de la boucle) et on a bien 1-1+2=2. Dans le second cas, il n'y a qu'une face, et on a cette fois 2-1+1=2.

Soit G un graphe possédant A + 1 arêtes et supprimons l'une des arêtes. Soit celle-ci sépare deux faces, soit ce n'est pas le cas. Dans le premier cas, la suppression de l'arête réunit ces deux faces, donc F diminue de 1. Par ailleurs, les sommets de l'arête supprimée sont forcément sur d'autres arêtes (sinon elle serait pendante et ne séparerait pas deux faces). Par conséquent, après suppression de l'arête, ces sommets sont toujours présents, le graphe est toujours connexe. Donc, pour le nouveau graphe plus petit, l'identité d'Euler est vérifiée par hypothèse de récurrence. Comme S - A + F n'a pas changé au cours de la réduction, il vaut 2 pour le graphe de départ.

Si l'arête supprimée ne séparait pas initialement deux faces, c'est qu'elle était sur une branche pendante. On peut alors supprimer à sa place la dernière des arêtes de la branche. Cela supprime un sommet (l'extrémité maintenant isolée de l'arête supprimée) et une arête, sans changer le nombre de faces. Là encore, le nombre S - A + F est inchangé et vaut 2 dans le petit graphe par hypothèse de récurrence, donc il vaut 2 aussi dans le graphe de départ.

Remarque -  L'identité d'Euler s'étend sans difficulté aux graphes non connexes. Si G est un graphe planaire plongé, possédant S sommets, A arêtes, F faces et k composantes connexes, on a

S - A + F = 1 + k

(le vérifier à titre d'exercice, en utilisant l'identité d'Euler pour les graphes connexes).

Grâce à cette relation, nous allons maintenant être en mesure de prouver que deux graphes particuliers ne sont pas planaires. Ce résultat est important, dans la mesure où les graphes en question jouent un rôle fondamental dans la théorie des graphes planaires (on pourrait dire, de manière un peu imprécise, qu'ils constituent l'ossature minimale de tout graphe planaire, comme le prouve le théorème de Kuratowski que nous énoncerons au paragraphe suivant). Par ailleurs, cela prouvera l'une des affirmations faites à la leçon précédente à propos du coloriage des cartes : il est impossible de trouver, dans une carte de géographie, cinq pays mutuellement frontaliers (c'est-à-dire tels que chacun d'entre eux partage avec les quatre autres une frontière non réduite à un point).

 

On appelle K3,3 le graphe à 6 (=3+3) sommets A, B, C, A', B' et C' tel que chacun des trois premiers soit relié de toutes les manières possibles à chacun des trois derniers (on l'appelle aussi le graphe des trois maisons et des trois usines). On appelle K5 le graphe à 5 sommets dans lequel chaque sommet est relié aux quatre autres (ce serait le graphe de voisinage d'une hypothétique carte géographique contredisant l'affirmation ci-dessus).

Théorème - Les graphes K3,3 et K5 ne sont pas planaires.

Démonstration - Nous la donnons pour K5. Supposons ce graphe planaire et imaginons-le dessiné dans le plan. Puisque ce graphe possède 5 sommets et 10 arêtes, il doit y avoir, d'après l'identité d'Euler, 7 faces. Mais chaque face est bordée par au moins trois arêtes (si une face n'était bordée que par deux arêtes, le graphe ne serait pas simple). Il en résulte que si l'on fait la somme, pour toutes les faces, des nombres d'arêtes qui les bordent, on trouve au moins 3F d'une part, mais on trouve aussi au maximum 2A d'autre part (chaque arête est comptée une ou deux fois, suivant qu'elle sépare deux faces ou non). Donc 2A 3F, ce qui donne ici 20 21, et une contradiction.

Remarque -  La démonstration ci-dessus ne permet pas de conclure pour K3,3 (on trouve 3F = 15 et 2A = 18). Mais dans ce cas-là, on remarque qu'aucune face ne peut être triangulaire (id est : bordée par trois arêtes), car dans le graphe K3,3, il n'y a pas de chemin fermé de longueur 3. La démonstration s'adapte alors pour donner 4F 2A et la contradiction souhaitée.

Remarque -  Dans le cas général, les arguments ci-dessus montrent que si G est un graphe planaire simple, 3(2 + A - S) 2A, ou encore A 3S - 6. Si le graphe est sans triangle, on obtient la meilleure inégalité A 2S - 4. Tout ceci correspond à l'intuition : pour que l'on puisse dessiner dans le plan toutes les arêtes de G sans que deux d'entre elles ne se coupent, il ne faut pas que G ait trop d'arêtes...

Remarque -  Tout graphe planaire simple contient au moins un sommet de degré inférieur ou égal à 5 (ceci est un autre résultat important utilisé à la question précédente). En effet, si pour tout sommet le degré valait au moins 6, la somme des degrés, égale à 2A d'après le lemme des poignées de main, serait au moins égale à 6S, alors que 2A 6S - 12 d'après la première inégalité de la remarque (b) ci-dessus.