Graphes planaires et formule d'Euler

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ce qui rend un graphe planaire

Un graphe est planaire lorsqu'il peut être dessiné sur une feuille de papier plane sans que deux arêtes se croisent. Chaque sommet devient un point, chaque arête devient une courbe qui relie ses deux extrémités, et les courbes n'ont le droit de se rencontrer qu'en un sommet qu'elles partagent. Un dessin qui respecte ces règles s'appelle un dessin plan ou un plongement du graphe, et un graphe muni d'un plongement fixé est un graphe plan.

La distinction entre les deux mots compte plus qu'il n'y paraît. Planaire est une propriété du graphe : on se demande s'il existe au moins un dessin sans croisement. Plan décrit un dessin particulier. Un graphe peut avoir un dessin plan parfaitement correct et aussi une centaine de dessins remplis de croisements, et aucun de ces mauvais dessins ne compte contre lui. Le graphe complet K4 en est le premier exemple classique. Dessiné comme un carré avec ses deux diagonales, il a deux diagonales qui se croisent. Placez un sommet au milieu du triangle formé par les trois autres et tous les croisements disparaissent, donc K4 est planaire.

La figure introduit aussi l'exemple fil rouge de cet article, le prisme triangulaire. Il a un triangle extérieur A, B, C, un triangle intérieur D, E, F, et trois rayons qui relient A à D, B à E et C à F :

V = {A, B, C, D, E, F}                                   6 sommets
E = {AB, BC, CA, DE, EF, FD, AD, BE, CF}                  9 arêtes

Trois remarques pratiques précisent ce dont la définition dépend et ce dont elle ne dépend pas. Premièrement, les boucles et les arêtes parallèles n'affectent jamais la planarité : une seconde copie d'une arête peut être dessinée comme une fine courbe juste à côté de la première, et une boucle comme une petite volute à côté de son sommet. Un multigraphe est planaire exactement quand son graphe simple sous-jacent l'est, c'est pourquoi les bornes de comptage énoncées plus loin dans cet article portent sur les graphes simples. Deuxièmement, le plan et la sphère sont interchangeables. La projection stéréographique transforme un dessin sur une sphère en un dessin dans le plan, et inversement, donc un graphe est planaire exactement quand il peut être dessiné sans croisement sur la surface d'une boule. Troisièmement, les courbes ne sont jamais nécessaires. Wagner en 1936 et Fáry en 1948 ont prouvé indépendamment que tout graphe planaire simple possède un dessin plan dans lequel chaque arête est un segment de droite, un résultat généralement appelé théorème de Fáry.

2. Faces : les régions créées par un dessin

Découpez un dessin plan dans le papier en suivant ses arêtes, et le papier se sépare en morceaux. Ces morceaux sont les faces du dessin. Exactement l'une d'elles est non bornée ; on l'appelle la face externe, et oublier de la compter est l'erreur la plus courante de tout ce sujet. Le prisme triangulaire a cinq faces : le triangle intérieur D, E, F, trois faces à quatre côtés A, B, E, D, B, C, F, E et C, A, D, F, et la face externe, qui se trouve à l'extérieur du triangle A, B, C.

La longueur (ou degré) d'une face est le nombre d'arêtes que vous parcourez en suivant son bord, avec une règle qui garde une comptabilité exacte : une arête qui a la même face de ses deux côtés, comme une arête d'un arbre, est parcourue deux fois et comptée deux fois. Avec cette règle, chaque arête apporte exactement deux au total, un pour chacun de ses côtés, et les faces obéissent à leur propre lemme des poignées de main :

somme des longueurs des faces = 2e

prisme :  3 + 4 + 4 + 4 + 3  =  18  =  2 × 9
          (triangle intérieur, trois quadrilatères, face externe bordée par A, B, C)

Cette identité reprend le lemme des poignées de main pour les sommets du guide sur les sommets et arêtes en mettant des faces à la place des sommets, et elle alimente toutes les bornes des sections 4 et 5. Les faces appartiennent à un dessin plutôt qu'au graphe, donc un graphe qui a plusieurs dessins plans peut avoir des faces de longueurs différentes dans chacun d'eux. Reliez deux sommets x et y par quatre chemins de longueurs 1, 2, 3 et 4. Disposés autour de x dans cet ordre, les chemins consécutifs bordent des faces de longueurs 3, 5, 7 et 5. Échangez les deux chemins du milieu et les longueurs des faces deviennent 4, 5, 6 et 5. Ce qui ne change pas, c'est le nombre de faces, quatre dans les deux dessins, et la section suivante prouve que ce n'est pas un hasard.

3. La formule d'Euler

Comptez les sommets, les arêtes et les faces de n'importe quel dessin plan connexe : une certaine combinaison des trois ne change jamais.

Formule d'Euler. Pour tout graphe plan connexe à v sommets, e arêtes et f faces, v − e + f = 2.

Pour le prisme, 6 − 9 + 5 = 2. Pour K4 dessiné sans croisement, 4 − 6 + 4 = 2. Pour un seul sommet, 1 − 0 + 1 = 2, puisque le plan vide qui l'entoure forme une seule face. La preuve est assez courte pour être donnée en entier, et elle mérite d'être lue, car la même idée, supprimer une arête et regarder ce qui change, traverse tout le reste du sujet.

Preuve. Fixez le nombre de sommets et raisonnez par récurrence sur le nombre d'arêtes. Un graphe connexe ayant le moins d'arêtes possible est un arbre, et un arbre a e = v − 1 (l'une des caractérisations réunies dans les arbres en théorie des graphes). Un arbre ne contient aucun cycle, donc son dessin n'entoure aucune région et il n'y a qu'une seule face. Alors v − (v − 1) + 1 = 2, comme annoncé.

Si le graphe connexe n'est pas un arbre, il contient un cycle. Choisissez une arête de ce cycle et supprimez-la. Le graphe reste connexe, car le reste du cycle relie toujours les deux extrémités de l'arête supprimée. Dans le dessin, le cycle est une courbe fermée et, d'après le théorème de Jordan, il sépare le plan en un intérieur et un extérieur. L'arête supprimée avait donc des faces différentes de ses deux côtés, l'une à l'intérieur du cycle et l'autre à l'extérieur, et la retirer fusionne ces deux faces en une seule. Ainsi e diminue de un et f diminue de un, et v − e + f reste inchangé. Par hypothèse de récurrence, le graphe plus petit vérifie la formule, donc le graphe d'origine aussi.

La formule a une conséquence qu'on lit facilement sans s'y arrêter. Le nombre de faces, f = e − v + 2, ne dépend que du graphe et non de la façon dont il est dessiné. C'est pourquoi les deux dessins du graphe à quatre chemins de la section 2 avaient tous deux quatre faces : avec v = 8 et e = 10, tout dessin plan de ce graphe a 10 − 8 + 2 = 4 faces. Si le graphe n'est pas connexe, la face externe est partagée par tous les morceaux, et la formule devient v − e + f = 1 + k pour un graphe à k composantes.

La formule est facile à vérifier par machine. La fonction ci-dessous prend un dessin rectiligne sans croisement, donné par des coordonnées, et trace chaque face en marchant le long des arêtes et en tournant toujours, à chaque sommet, vers l'arête suivante dans le sens des aiguilles d'une montre. Chaque arête a deux côtés, et chaque côté est parcouru exactement une fois.

from math import atan2

def faces(pos, edges):
    """Trace les faces d'un dessin rectiligne sans croisement d'un graphe connexe."""
    nbrs = {v: [] for v in pos}
    for u, v in edges:
        nbrs[u].append(v)
        nbrs[v].append(u)
    for v, ws in nbrs.items():               # voisins dans le sens antihoraire
        x, y = pos[v]
        ws.sort(key=lambda w: atan2(pos[w][1] - y, pos[w][0] - x))
    seen, found = set(), []
    for u, v in edges:
        for dart in ((u, v), (v, u)):        # chaque arête a deux côtés
            face = []
            while dart not in seen:
                seen.add(dart)
                a, b = dart
                face.append(a)
                ws = nbrs[b]
                dart = (b, ws[ws.index(a) - 1])  # en b, tourner vers l'arête suivante dans le sens horaire
            if face:
                found.append(face)
    return found

pos = {'A': (0, 4), 'B': (-3.5, -2), 'C': (3.5, -2),
       'D': (0, 1.6), 'E': (-1.4, -0.8), 'F': (1.4, -0.8)}
edges = [('A', 'B'), ('B', 'C'), ('C', 'A'), ('D', 'E'), ('E', 'F'),
         ('F', 'D'), ('A', 'D'), ('B', 'E'), ('C', 'F')]
fs = faces(pos, edges)
v, e, f = len(pos), len(edges), len(fs)
print(v, e, f, v - e + f)
# 6 9 5 2
print(sorted(len(face) for face in fs))
# [3, 3, 4, 4, 4]

Les cinq longueurs de faces sont exactement celles comptées dans la section 2, et leur somme vaut 18 = 2e. La même procédure de tracé, appliquée à une liste abstraite d'ordres de voisins plutôt qu'à des coordonnées, est la façon dont les bibliothèques de planarité stockent un plongement : un plongement d'un graphe est entièrement décrit par l'ordre cyclique des arêtes autour de chaque sommet, une description appelée système de rotation.

Les polyèdres, et l'origine de la formule

Euler n'a pas énoncé la formule pour des graphes. Il l'a énoncée pour des polyèdres, des solides bornés par des faces planes, dans une lettre à Christian Goldbach en novembre 1750, et l'a publiée dans deux articles du journal de l'Académie de Saint-Pétersbourg, dans le volume daté de 1752 et 1753, qui a été imprimé en 1758. Dessinez un polyèdre convexe dans le plan en regardant à travers l'une de ses faces, qui devient alors la face externe : ses coins, ses arêtes et ses faces deviennent les sommets, les arêtes et les faces d'un graphe plan. Les cinq solides de Platon donnent tous la même réponse :

L'histoire comporte deux rebondissements bien connus. René Descartes avait écrit une relation équivalente, formulée en termes d'angles, dans un manuscrit aujourd'hui perdu ; une copie que Leibniz en avait faite à Paris en 1675 ou 1676 a été redécouverte au XIXe siècle et publiée en 1859–60. Et l'argument d'Euler lui-même, qui tranchait les coins du solide un par un, n'était pas une preuve complète selon les critères modernes. Adrien-Marie Legendre a donné la première preuve complète en 1794, en utilisant les aires de polygones tracés sur une sphère, et Augustin-Louis Cauchy en a publié une autre en 1813, qui aplatit le polyèdre en un réseau dans le plan et le démonte pièce par pièce, dans un esprit proche de l'argument ci-dessus. Imre Lakatos a construit son livre Proofs and Refutations (1976) autour des étranges « polyèdres » qui mettent la formule en défaut, comme un cadre de tableau, dont la surface a un trou. L'article sur l'histoire de la théorie des graphes place ce résultat à côté de l'autre contribution fondatrice d'Euler, les ponts de Königsberg.

4. Combien d'arêtes un graphe planaire peut-il avoir ?

La formule d'Euler devient une limite stricte sur le nombre d'arêtes dès qu'on la combine avec le lemme des poignées de main pour les faces. L'argument tient en trois lignes, les plus utiles de la théorie des graphes planaires.

Théorème. Un graphe planaire simple à v ≥ 3 sommets a au plus 3v − 6 arêtes. S'il n'a en outre aucun triangle, il a au plus 2v − 4 arêtes.

Preuve. Prenez un dessin plan et supposez d'abord que le graphe est connexe. Dans un graphe simple ayant au moins trois sommets, chaque face a une longueur d'au moins 3 : une face de longueur 1 exigerait une boucle et une face de longueur 2 exigerait deux arêtes parallèles, sauf lorsque le graphe entier se réduit à une seule arête, ce que v ≥ 3 exclut. En sommant sur toutes les faces, 3f ≤ 2e. La formule d'Euler donne f = 2 − v + e, donc 3(2 − v + e) ≤ 2e, ce qui se réécrit e ≤ 3v − 6. Si le graphe n'a aucun triangle, chaque face a une longueur d'au moins 4, donc 4f ≤ 2e et la même substitution donne e ≤ 2v − 4. On peut ajouter des arêtes entre les composantes d'un graphe planaire non connexe sans créer de croisement, et ajouter des arêtes ne fait que rendre l'inégalité plus difficile à satisfaire, donc les bornes valent aussi pour lui.

La seconde borne couvre tout graphe biparti, puisqu'un graphe biparti n'a aucun cycle impair et en particulier aucun triangle. Les deux bornes sont des cas particuliers d'une même inégalité. Si le plus court cycle d'un graphe planaire connexe, sa maille, a pour longueur g, chaque face a une longueur d'au moins g, et les trois mêmes lignes donnent

e ≤ g(v − 2) / (g − 2)

g = 3   →   e ≤ 3v − 6        (tout graphe planaire simple, v ≥ 3)
g = 4   →   e ≤ 2v − 4        (aucun triangle, donc tout graphe biparti planaire)
g = 5   →   e ≤ 5(v − 2)/3     (aucun cycle de longueur 3 ou 4)

La première borne est atteinte. Un graphe plan dans lequel chaque face, y compris la face externe, est un triangle s'appelle une triangulation, et pour une triangulation 3f = 2e est une égalité, donc e = 3v − 6 exactement. L'octaèdre (6 sommets, 12 arêtes) et l'icosaèdre (12 sommets, 30 arêtes) sont des triangulations. Ajouter n'importe quelle arête à une triangulation la rend non planaire, c'est pourquoi les triangulations sont aussi appelées graphes planaires maximaux. Le prisme n'est pas maximal : il a 9 arêtes pour un plafond de 3 × 6 − 6 = 12, et trois diagonales, une dans chaque face quadrilatérale, le porteraient à 12.

Deux corollaires servent constamment. Le premier est que les graphes planaires sont creux : le nombre d'arêtes ne croît que linéairement avec le nombre de sommets, donc un graphe planaire à un million de sommets a moins de trois millions d'arêtes, alors qu'un graphe quelconque à un million de sommets peut en avoir près de 500 milliards. C'est pourquoi les algorithmes sur les graphes planaires se mesurent en fonction de v seul, et pourquoi les listes d'adjacence, plutôt que les matrices, sont le format de stockage naturel, comme l'explique le guide sur la représentation des graphes. Le second est le lemme du degré cinq :

Tout graphe planaire simple possède un sommet de degré au plus 5.

La somme des degrés vaut 2e, et 2e ≤ 6v − 12 lorsque v ≥ 3, donc le degré moyen est inférieur à 6 et au moins un sommet doit avoir un degré de 5 ou moins. Les graphes à un ou deux sommets vérifient trivialement le lemme. Le lemme est optimal : chaque sommet de l'icosaèdre est de degré exactement 5. C'est le moteur des théorèmes de coloration de la section 8.

5. Pourquoi K₅ et K₃,₃ ne sont pas planaires

Les bornes sur les arêtes transforment « aucun dessin ne fonctionne », une affirmation sur une infinité de dessins, en un calcul d'une ligne.

Le graphe complet K5 a v = 5 et e = 10. Un graphe planaire à 5 sommets a au plus 3 × 5 − 6 = 9 arêtes, donc K5 n'est pas planaire.

Le graphe biparti complet K3,3 a v = 6 et e = 9. La première borne autorise 12 arêtes, elle ne dit donc rien. Mais K3,3 est biparti et n'a donc aucun triangle, et la seconde borne n'en autorise que 2 × 6 − 4 = 8. Neuf arêtes, c'est une de trop. C'est le classique problème des trois maisons, qui demande de relier trois maisons à l'eau, au gaz et à l'électricité sans qu'aucun tuyau ni aucun câble ne se croise. Il apparaît sous le titre « Water, Gas, and Electricity » (eau, gaz et électricité) dans le livre de Henry Dudeney Amusements in Mathematics paru en 1917, et le guide sur les graphes bipartis donne le même argument du point de vue de la bipartition.

La comparaison avec le prisme est la partie instructive. Les deux graphes ont six sommets et neuf arêtes, et dans les deux chaque sommet est de degré 3, donc aucun décompte de sommets, d'arêtes ou de degrés ne permet de les distinguer. Ce qui les sépare, c'est la forme de leurs faces : le prisme peut utiliser deux triangles, alors que K3,3 aurait besoin que chaque face ait au moins quatre côtés, et il n'y a pas assez de place pour cela.

Les deux graphes ne sont non planaires que de justesse. Chacun peut être dessiné avec exactement un croisement, comme le montre la figure, donc leur nombre de croisements vaut 1. Supprimer n'importe quelle arête de l'un ou l'autre graphe laisse un graphe planaire. Ce sont, en un sens précis, les plus petits obstacles à la planarité, et la section suivante explique que ce sont les seuls.

Les bornes de comptage ont une limite qu'il faut énoncer clairement : ce sont des conditions nécessaires, pas suffisantes. Un graphe qui les viole n'est certainement pas planaire ; un graphe qui les respecte peut quand même être non planaire. Prenez K3,3 et ajoutez une arête entre deux sommets du même côté. Le nouveau graphe a 6 sommets et 10 arêtes et contient désormais des triangles, donc la seule borne qui s'applique est 3v − 6 = 12, qu'il respecte. Pourtant il contient K3,3, donc il ne peut pas être planaire. Le graphe de Petersen se situe entre les deux. Avec 10 sommets et 15 arêtes, il passe à la fois 3v − 6 = 24 et 2v − 4 = 16, mais sa maille vaut 5, et la borne de la maille n'autorise que 5 × 8 / 3, soit environ 13,3, donc 13 arêtes. Quinze arêtes, c'est trop, et le graphe de Petersen n'est pas planaire.

6. Les théorèmes de Kuratowski et de Wagner

Deux opérations relient un graphe aux petits obstacles qu'il contient. Une subdivision d'un graphe remplace des arêtes par des chemins, en insérant le long de ceux-ci de nouveaux sommets de degré 2. Subdiviser une arête ne change pas le fait qu'un dessin ait des croisements ou non, puisque les nouveaux sommets se posent simplement sur la courbe, donc une subdivision de K5 ou de K3,3 est tout aussi non planaire que l'original. Un graphe planaire ne peut pas non plus contenir de sous-graphe non planaire, car supprimer des parties d'un dessin plan laisse un dessin plan. En 1930, Kazimierz Kuratowski a prouvé que ces obstacles évidents sont les seuls.

Théorème de Kuratowski (1930). Un graphe est planaire si et seulement s'il ne contient aucun sous-graphe qui soit une subdivision de K5 ou de K3,3.

La moitié « seulement si » est le sens facile qui vient d'être décrit. La moitié « si » est la plus profonde : tout graphe qui ne peut pas être dessiné dans le plan doit contenir l'une de ces deux formes, éventuellement avec ses arêtes étirées en longs chemins. Une seconde opération donne une version plus nette. Contracter une arête fusionne ses deux extrémités en un seul sommet adjacent à tous leurs anciens voisins, et un graphe obtenu à partir de G en supprimant des sommets et des arêtes et en contractant des arêtes est un mineur de G. La contraction préserve aussi la planarité, puisqu'on peut réduire une arête d'un dessin plan à un point.

Théorème de Wagner (1937). Un graphe est planaire si et seulement s'il n'a ni K5 ni K3,3 comme mineur.

Les deux théorèmes sont équivalents, mais ils ne sont pas interchangeables sur des exemples, et le graphe de Petersen montre la différence. Contractez les cinq rayons qui relient son 5-cycle extérieur à son pentagramme intérieur, et les dix sommets se réduisent à cinq, chacun adjacent aux quatre autres : le graphe de Petersen admet K5 comme mineur. En revanche, il ne contient aucune subdivision de K5, car une subdivision de K5 exige cinq sommets de degré 4 et chaque sommet du graphe de Petersen est de degré 3. Le théorème de Kuratowski reste vérifié, grâce à l'autre forme. Supprimez n'importe quel sommet : les 9 sommets et 12 arêtes restants forment une subdivision de K3,3 : trois des sommets sont de degré 2 et se trouvent sur des chemins, et les six autres se répartissent en deux côtés de trois.

La forme de Wagner a ouvert une histoire bien plus vaste. La planarité est close par mineurs : tout mineur d'un graphe planaire est planaire. Neil Robertson et Paul Seymour ont prouvé, dans une série d'articles publiés entre 1983 et 2004, que toute famille de graphes close par mineurs est caractérisée par une liste finie de mineurs interdits, de même que les graphes planaires sont caractérisés par la liste K5, K3,3. Le théorème garantit qu'une telle liste existe et qu'elle est finie, mais il ne dit ni quelle est sa longueur ni comment la trouver.

7. Tester la planarité

Les bornes de comptage de la section 4 donnent un premier test instantané. Elles ne peuvent pas prouver qu'un graphe est planaire, mais lorsqu'elles échouent, elles prouvent qu'il ne l'est pas, et leur vérification ne coûte presque rien. La fonction ci-dessous calcule la maille par un parcours en largeur depuis chaque sommet et applique la borne de la maille, qui contient à la fois 3v − 6 et 2v − 4 comme cas particuliers.

from collections import deque

def girth(adj):
    """Longueur du plus court cycle (inf pour une forêt) : BFS depuis chaque sommet."""
    best = float('inf')
    for s in adj:
        dist, parent = {s: 0}, {s: None}
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for w in adj[u]:
                if w not in dist:
                    dist[w], parent[w] = dist[u] + 1, u
                    queue.append(w)
                elif parent[u] != w:         # une arête hors de l'arbre ferme un cycle
                    best = min(best, dist[u] + dist[w] + 1)
    return best

def euler_filter(adj):
    """False : certainement non planaire. True : seulement 'non exclu'. Graphes simples et connexes."""
    n = len(adj)
    m = sum(len(ws) for ws in adj.values()) // 2
    g = girth(adj)
    if g == float('inf'):
        return True                          # les arbres sont toujours planaires
    return m * (g - 2) <= g * (n - 2)        # g = 3 donne 3n - 6, g = 4 donne 2n - 4

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)
    return adj

prism = graph(['AB', 'BC', 'CA', 'DE', 'EF', 'FD', 'AD', 'BE', 'CF'])
k5 = graph([(i, j) for i in range(5) for j in range(i + 1, 5)])
k33 = graph([(a, b) for a in 'abc' for b in 'xyz'])
petersen = graph([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                 + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
k33_plus = graph([(a, b) for a in 'abc' for b in 'xyz'] + [('a', 'b')])
for name, adj in [('prism', prism), ('K5', k5), ('K3,3', k33),
                  ('Petersen', petersen), ('K3,3 + edge', k33_plus)]:
    print(f'{name:12} girth {girth(adj)}  passes: {euler_filter(adj)}')
# prism        girth 3  passes: True
# K5           girth 3  passes: False
# K3,3         girth 4  passes: False
# Petersen     girth 5  passes: False
# K3,3 + edge  girth 3  passes: True

Le filtre rejette K5, K3,3 et le graphe de Petersen, et il laisse passer le prisme, ce qui est correct, ainsi que K3,3 avec une arête supplémentaire, ce qui ne l'est pas. Le « passes » de la sortie signifie seulement « non exclu ». Chaque parcours en largeur prend un temps O(v + e) et le filtre en lance un depuis chaque sommet, donc il coûte O(v(v + e)) ; un graphe qui échoue au test moins coûteux e ≤ 3v − 6 peut être rejeté avant même de calculer la maille.

Une réponse complète exige un véritable algorithme de planarité. Le théorème de Kuratowski n'en fournit pas directement un qui soit efficace, car chercher des subdivisions coûte cher. Hopcroft et Tarjan ont publié le premier test de planarité en temps linéaire en 1974, en s'appuyant sur le parcours en profondeur, et des algorithmes ultérieurs ont rendu l'idée plus simple à implémenter : la méthode d'ajout d'arêtes de Boyer et Myrvold, de 2004, et le critère de planarité gauche-droite de de Fraysseix et Rosenstiehl, sur lequel repose l'implémentation de NetworkX. Une bonne implémentation renvoie un certificat dans les deux cas : un plongement plan lorsque le graphe est planaire, et un sous-graphe de Kuratowski lorsqu'il ne l'est pas.

import networkx as nx

def count_faces(embedding):
    seen, f = set(), 0
    for u, v in embedding.edges():           # chaque demi-arête borde exactement une face
        if (u, v) not in seen:
            embedding.traverse_face(u, v, mark_half_edges=seen)
            f += 1
    return f

tests = [('prism', nx.circular_ladder_graph(3)), ('K5', nx.complete_graph(5)),
         ('K3,3', nx.complete_bipartite_graph(3, 3)), ('Petersen', nx.petersen_graph()),
         ('K3,3 + edge', nx.complete_bipartite_graph(3, 3))]
tests[-1][1].add_edge(0, 1)
for name, G in tests:
    planar, cert = nx.check_planarity(G, counterexample=True)
    if planar:
        print(f'{name:12} planar, {count_faces(cert)} faces')
    else:
        branch = sum(1 for _, d in cert.degree() if d > 2)
        kind = 'K5' if branch == 5 else 'K3,3'
        print(f'{name:12} not planar: a subdivision of {kind}, '
              f'{cert.number_of_nodes()} vertices, {cert.number_of_edges()} edges')
# prism        planar, 5 faces
# K5           not planar: a subdivision of K5, 5 vertices, 10 edges
# K3,3         not planar: a subdivision of K3,3, 6 vertices, 9 edges
# Petersen     not planar: a subdivision of K3,3, 9 vertices, 12 edges
# K3,3 + edge  not planar: a subdivision of K3,3, 6 vertices, 9 edges

Chaque réponse s'accompagne de sa preuve. Pour le prisme, le certificat est un plongement, stocké sous forme de système de rotation, et son tracé donne 5 faces, comme l'exige la formule d'Euler. Pour K5 et K3,3 le certificat est le graphe entier. Pour le graphe de Petersen, c'est une subdivision de K3,3 utilisant 9 des 10 sommets, exactement la structure du panneau de droite de la figure précédente, et ce ne pourrait jamais être une subdivision de K5 puisqu'aucun sommet n'est de degré 4. Les sous-graphes de Kuratowski ne sont pas uniques, donc une autre bibliothèque ou une autre version peut en renvoyer un différent ; chacun d'eux est une preuve valide.

8. Coloration des graphes planaires et théorème des quatre couleurs

C'est en coloration que les graphes planaires ont leur théorème le plus célèbre. Une coloration propre donne à chaque sommet une couleur de sorte que les deux extrémités de chaque arête diffèrent, et le plus petit nombre de couleurs qui suffit est le nombre chromatique, que le guide de la coloration de graphes traite en détail. Colorier une carte de sorte que les pays voisins diffèrent est le même problème sur le graphe planaire de la carte, avec un sommet par pays et une arête pour chaque frontière commune.

Le lemme du degré cinq de la section 4 donne déjà une borne avec une preuve élémentaire.

Théorème des six couleurs. Tout graphe planaire peut être colorié proprement avec au plus six couleurs.

Retirez un sommet de degré au plus 5, qui existe d'après le lemme, et coloriez le reste du graphe, qui est toujours planaire, par récurrence. Puis remettez le sommet. Il a au plus cinq voisins, donc au moins l'une des six couleurs est libre pour lui. La preuve est un algorithme : retirez de façon répétée un sommet de plus petit degré, puis coloriez les sommets dans l'ordre inverse de leur retrait.

def six_colour(adj):
    """Colorie un graphe planaire simple avec au plus 6 couleurs (glouton, plus petit degré en dernier)."""
    deg = {v: len(ws) for v, ws in adj.items()}
    removed, order = set(), []
    while len(order) < len(adj):
        v = min((u for u in adj if u not in removed), key=deg.get)  # un degré <= 5 existe
        removed.add(v)
        order.append(v)
        for w in adj[v]:
            if w not in removed:
                deg[w] -= 1
    colour = {}
    for v in reversed(order):                # au plus 5 voisins sont déjà coloriés
        used = {colour[w] for w in adj[v] if w in colour}
        colour[v] = min(c for c in range(6) if c not in used)
    return colour

# L'icosaèdre : 12 sommets, 30 arêtes, chaque sommet de degré exactement 5.
edges = []
for i in range(5):
    j = (i + 1) % 5
    top, a, b, c, d, bottom = 0, 1 + i, 1 + j, 6 + i, 6 + j, 11
    edges += [(top, a), (a, b), (a, c), (a, d), (c, d), (c, bottom)]
adj = {v: [] for v in range(12)}
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
colour = six_colour(adj)
print(len(edges), {len(ws) for ws in adj.values()}, max(colour.values()) + 1)
# 30 {5} 4
print(all(colour[u] != colour[v] for u, v in edges))
# True

Sur l'icosaèdre, où chaque sommet est de degré exactement 5, la méthode utilise quatre couleurs, ce qui est le minimum, puisque chaque sommet et les cinq voisins qui l'entourent en exigent déjà quatre. L'heuristique d'ordre ne fait pas toujours aussi bien, mais elle n'a jamais besoin de plus de six couleurs.

Descendre à cinq couleurs demande une idée de plus. En 1879, Alfred Kempe a publié une preuve que quatre couleurs suffisent toujours, fondée sur l'échange des deux couleurs le long d'une chaîne de sommets coloriés alternativement, appelée aujourd'hui une chaîne de Kempe. En 1890, Percy Heawood a trouvé une faille dans l'argument de Kempe et, dans le même article, a sauvé la technique des chaînes pour prouver que cinq couleurs suffisent toujours. La question elle-même remonte à 1852, lorsque Francis Guthrie a remarqué que quatre couleurs suffisaient pour une carte des comtés d'Angleterre et s'est demandé si c'était toujours vrai ; son frère Frederick a transmis la question à Augustus De Morgan.

Théorème des quatre couleurs (Appel et Haken, 1976). Tout graphe planaire peut être colorié proprement avec au plus quatre couleurs.

Kenneth Appel et Wolfgang Haken ont annoncé la preuve en 1976 et l'ont publiée en 1977. Elle ramène le problème à un ensemble fini de configurations, 1 482 dans la version publiée, et vérifie chacune d'elles par ordinateur, au prix d'environ 1 200 heures de calcul machine. Ce fut le premier grand théorème dont la preuve ne pouvait pas être vérifiée à la main. La preuve a été simplifiée par Robertson, Sanders, Seymour et Thomas en 1997, qui ont réduit l'ensemble à 633 configurations, et en 2005 Georges Gonthier a achevé une preuve entièrement formelle, vérifiée ligne par ligne dans l'assistant de preuve Coq, levant tout doute persistant sur la partie informatique.

Quatre est le bon nombre : K4 est planaire et exige quatre couleurs, car ses quatre sommets sont deux à deux adjacents. Trois couleurs ne suffisent pas en général, et décider si un graphe planaire donné peut être colorié avec trois couleurs est NP-complet, comme l'ont montré Garey, Johnson et Stockmeyer en 1976, même lorsque chaque sommet est de degré au plus 4. Dans l'autre sens, Grötzsch a prouvé en 1959 que tout graphe planaire sans triangle est 3-coloriable. Deux couleurs, enfin, suffisent exactement pour les graphes bipartis, planaires ou non.

9. Graphes duaux

Tout graphe plan G a un partenaire, son dual G*. Placez un nouveau sommet à l'intérieur de chaque face de G. Puis, pour chaque arête de G, tracez une arête duale qui la croise et relie les sommets duaux des deux faces situées de part et d'autre. Si une arête a la même face des deux côtés, son arête duale est une boucle, et deux faces qui partagent plusieurs arêtes sont reliées par des arêtes duales parallèles, donc le dual est en général un multigraphe.

Le prisme a cinq faces, donc son dual a cinq sommets. Le sommet dual du triangle intérieur D, E, F est relié aux trois quadrilatères, le sommet dual de la face externe est relié aux trois mêmes, et les trois quadrilatères sont reliés entre eux en triangle. Ce dual est la bipyramide triangulaire, formée de deux pyramides triangulaires collées par leur base : 5 sommets, 9 arêtes et 6 faces triangulaires, une face pour chacun des 6 sommets du prisme.

La dualité échange les rôles des sommets et des faces et conserve les arêtes : G* a f sommets, e arêtes et v faces, donc la formule d'Euler se lit de la même façon pour les deux. Pour les graphes plans connexes, le dual du dual est à nouveau le graphe d'origine. Les solides de Platon s'associent par dualité, le cube avec l'octaèdre et le dodécaèdre avec l'icosaèdre, tandis que le tétraèdre est son propre dual.

Le dual traduit un type de structure en un autre :

• La coloration des faces devient coloration des sommets. Colorier les régions d'une carte de sorte que les régions voisines diffèrent revient à colorier les sommets du graphe dual. C'est ainsi que le théorème des quatre couleurs pour les cartes devient un énoncé sur les graphes planaires.
• Les cycles deviennent des coupes. Les arêtes d'un cycle de G correspondent à un ensemble minimal d'arêtes duales dont la suppression déconnecte G*, car le cycle sépare les faces qui sont à l'intérieur de celles qui sont à l'extérieur. Dans les réseaux planaires, cela transforme un problème de coupe minimum en un problème de plus court cycle dans le dual, l'une des raisons pour lesquelles le flot maximum se calcule plus vite sur les graphes planaires qu'en général (voir flot maximum et coupe minimum).
• Les arbres couvrants vont par paires. Si T est un arbre couvrant de G, les duaux des arêtes qui ne sont pas dans T forment un arbre couvrant de G*. En comptant les arêtes, on obtient (v − 1) + (f − 1) = e, c'est-à-dire à nouveau la formule d'Euler, par une tout autre voie.

Une mise en garde accompagne la définition. Le dual est construit à partir d'un dessin, pas du graphe, donc un graphe planaire qui a plusieurs plongements différents peut avoir plusieurs duaux non isomorphes. Whitney a prouvé en 1932 et 1933 que cela ne peut pas arriver lorsqu'un graphe planaire est 3-connexe au sens où il reste connexe après la suppression de deux sommets quelconques : son plongement sur la sphère est alors essentiellement unique, et son dual aussi. Le prisme est 3-connexe, c'est pourquoi son dual est bien défini. D'après le théorème de Steinitz, les graphes planaires 3-connexes sont aussi exactement les graphes des polyèdres convexes, ce qui referme la boucle en revenant à Euler.

10. Où l'on rencontre des graphes planaires

La planarité est une propriété géométrique : elle apparaît donc partout où un réseau doit être disposé sur une surface, et partout où une surface est découpée en régions.

Les circuits sont l'application classique. Sur un circuit imprimé à une seule couche, les pistes de cuivre ne peuvent pas se croiser sans provoquer de court-circuit, donc le graphe des connexions doit être planaire. Quand il ne l'est pas, les concepteurs font passer certaines pistes sur une seconde couche et relient les couches par des trous percés appelés vias, ou font passer une piste au-dessus d'une autre avec un fil de pontage. Le nombre minimum de croisements dans un dessin quelconque d'un graphe, son nombre de croisements, mesure à quel point un circuit est loin d'être planaire, et le nombre de couches planaires nécessaires pour accueillir toutes ses arêtes est son épaisseur.

Les cartes fournissent la deuxième. Une carte de pays est un graphe plan dont les faces sont les pays, et son dual a un sommet par pays et une arête par frontière commune. Colorier les pays revient à colorier le dual, et le théorème des quatre couleurs plafonne le nombre de couleurs à quatre, à condition que chaque pays soit une seule région connexe. Les atlas réels enfreignent cette condition : un pays en plusieurs morceaux, comme les États-Unis avec l'Alaska ou la Russie avec Kaliningrad, doit avoir la même couleur à deux endroits, et les cartes soumises à de telles contraintes peuvent nécessiter plus de quatre couleurs.

Les réseaux routiers et les séparateurs fournissent la troisième. Lipton et Tarjan ont prouvé en 1979 que tout graphe planaire à n sommets peut être scindé en deux parties, aucune ne dépassant 2n/3 sommets, en retirant seulement O(√n) sommets. Les petits séparateurs sont la base des algorithmes « diviser pour régner » sur les graphes planaires, y compris des calculs de plus court chemin plus rapides. Les réseaux routiers ne sont pas exactement planaires, à cause des ponts et des tunnels, mais eux aussi peuvent généralement être découpés en grands morceaux en retirant peu de carrefours, et c'est sur cette propriété que reposent les calculateurs d'itinéraires fondés sur le partitionnement.

Les maillages fournissent la dernière. Un maillage triangulaire fermé d'une surface en forme de sphère, sans lacune ni anse, vérifie v − e + f = 2, et puisque chaque triangle a trois arêtes et que chaque arête borde deux triangles, 3f = 2e. Ensemble, ces égalités imposent f = 2v − 4 et e = 3v − 6. Un maillage d'une telle surface qui ne respecte pas ces décomptes a une lacune, un triangle manquant ou un sommet dupliqué quelque part, ce qui fait de ces décomptes un contrôle de cohérence peu coûteux lorsqu'un maillage est importé ou réparé.

11. Au-delà du plan : croisements et surfaces

Un graphe non planaire n'est pas la fin de l'histoire. Deux questions naturelles mesurent à quel point il est loin d'être planaire.

La première est le nombre de croisements cr(G), le plus petit nombre de croisements dans un dessin quelconque. Les graphes planaires ont un nombre de croisements égal à 0, et K5 et K3,3 ont un nombre de croisements égal à 1. Le calculer est NP-difficile en général, et même pour les graphes complets, les valeurs exactes ne sont connues que pour de petits cas.

La seconde consiste à dessiner sur une autre surface. Un tore, la surface d'un beignet en anneau, a un trou, et ce trou permet aux arêtes de se contourner. Aussi bien K5 que K3,3 peuvent être dessinés sur un tore sans croisement, et c'est aussi le cas de K7. La formule d'Euler se généralise : un graphe plongé dans une surface à g trous, de sorte que chaque face soit un disque, vérifie

v − e + f = 2 − 2g

plan ou sphère    g = 0 :  v − e + f = 2
tore              g = 1 :  v − e + f = 0         K7 sur un tore :  7 − 21 + 14 = 0

Le nombre 2 − 2g est la caractéristique d'Euler de la surface, l'un des premiers invariants de la topologie. Heawood l'a utilisée dans son article de 1890 pour borner le nombre de couleurs nécessaires sur une surface à g trous, et la borne a été prouvée exacte pour tout g ≥ 1 par Ringel et Youngs en 1968. Pour le tore, la réponse est 7, et K7 montre que sept couleurs peuvent réellement être nécessaires. Le plan, où la même formule donnerait 4, était le seul cas que leurs travaux ne couvraient pas ; c'était le théorème des quatre couleurs.

12. Erreurs fréquentes

13. Glossaire

15. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Euler, L. (1758). "Elementa doctrinae solidorum." Novi Commentarii Academiae Scientiarum Petropolitanae 4 (1752/53), 109 à 140. La formule des polyèdres, énoncée sans preuve.
2. Euler, L. (1758). "Demonstratio nonnullarum insignium proprietatum, quibus solida hedris planis inclusa sunt praedita." Novi Commentarii Academiae Scientiarum Petropolitanae 4 (1752/53), 140 à 160. La preuve d'Euler par troncature des coins.
3. Legendre, A.-M. (1794). Éléments de géométrie. Paris. La première preuve complète, par les polygones sphériques.
4. Cauchy, A.-L. (1813). "Recherches sur les polyèdres. Premier mémoire." Journal de l'École Polytechnique 9 (16e cahier), 68 à 86.
5. Kempe, A. B. (1879). "On the Geographical Problem of the Four Colours." American Journal of Mathematics 2(3), 193 à 200.
6. Heawood, P. J. (1890). "Map-Colour Theorem." Quarterly Journal of Pure and Applied Mathematics 24, 332 à 338. La faille dans la preuve de Kempe, le théorème des cinq couleurs et la borne pour les autres surfaces.
7. Dudeney, H. E. (1917). Amusements in Mathematics. Londres : Thomas Nelson. Problème 251, "Water, Gas, and Electricity."
8. Steinitz, E. (1922). "Polyeder und Raumeinteilungen." Dans Encyklopädie der mathematischen Wissenschaften, Band 3 (Geometrie), Teil 3AB12, 1 à 139. Leipzig : Teubner.
9. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 à 283.
10. Whitney, H. (1932). "Non-separable and Planar Graphs." Transactions of the American Mathematical Society 34(2), 339 à 362. Les duaux combinatoires.
11. Whitney, H. (1933). "2-Isomorphic Graphs." American Journal of Mathematics 55, 245 à 254. L'unicité du plongement des graphes planaires 3-connexes.
12. Wagner, K. (1936). "Bemerkungen zum Vierfarbenproblem." Jahresbericht der Deutschen Mathematiker-Vereinigung 46, 26 à 32. Les dessins rectilignes.
13. Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe." Mathematische Annalen 114, 570 à 590. La planarité par les mineurs interdits.
14. Fáry, I. (1948). "On Straight Line Representation of Planar Graphs." Acta Scientiarum Mathematicarum (Szeged) 11, 229 à 233.
15. Grötzsch, H. (1959). "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel." Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe 8, 109 à 120.
16. Ringel, G. et Youngs, J. W. T. (1968). "Solution of the Heawood Map-Coloring Problem." Proceedings of the National Academy of Sciences 60(2), 438 à 445.
17. Hopcroft, J. et Tarjan, R. (1974). "Efficient Planarity Testing." Journal of the ACM 21(4), 549 à 568.
18. Garey, M. R., Johnson, D. S. et Stockmeyer, L. (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science 1(3), 237 à 267. La 3-colorabilité des graphes planaires est NP-complète.
19. Lakatos, I. (1976). Proofs and Refutations: The Logic of Mathematical Discovery. Édité par J. Worrall et E. Zahar. Cambridge : Cambridge University Press.
20. Appel, K. et Haken, W. (1977). "Every Planar Map is Four Colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3), 429 à 490.
21. Appel, K., Haken, W. et Koch, J. (1977). "Every Planar Map is Four Colorable. Part II: Reducibility." Illinois Journal of Mathematics 21(3), 491 à 567.
22. Lipton, R. J. et Tarjan, R. E. (1979). "A Separator Theorem for Planar Graphs." SIAM Journal on Applied Mathematics 36(2), 177 à 189.
23. Federico, P. J. (1982). Descartes on Polyhedra: A Study of the De Solidorum Elementis. New York : Springer. Le manuscrit de Descartes et la copie de Leibniz.
24. de Fraysseix, H. et Rosenstiehl, P. (1985). "A Characterization of Planar Graphs by Trémaux Orders." Combinatorica 5(2), 127 à 135. Le critère gauche-droite.
25. Robertson, N., Sanders, D. P., Seymour, P. et Thomas, R. (1997). "The Four-Colour Theorem." Journal of Combinatorial Theory, Series B 70(1), 2 à 44.
26. Boyer, J. M. et Myrvold, W. J. (2004). "On the Cutting Edge: Simplified O(n) Planarity by Edge Addition." Journal of Graph Algorithms and Applications 8(3), 241 à 273.
27. Robertson, N. et Seymour, P. D. (2004). "Graph Minors. XX. Wagner's Conjecture." Journal of Combinatorial Theory, Series B 92(2), 325 à 357.
28. Gonthier, G. (2008). "Formal Proof: The Four-Color Theorem." Notices of the American Mathematical Society 55(11), 1382 à 1393.
29. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Springer. Chapitres 10 et 11 sur les graphes planaires et le problème des quatre couleurs.
30. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer. Chapitre 4 sur les graphes planaires.