Graphes planaires

Un graphe est dit "planaire" quand il peut être tracé sur un plan sans que ses arêtes se croisent.

Problème : soient trois usines produisant eau, gaz et électricité et trois villes.
Relier chaque ville à chaque usine sans que les canalisations ne se croisent.

C'est impossible, le graphe biparti K_3,3 n'est pas planaire.
De même les graphes complets d'ordre 5 et plus ne sont pas planaires.

Théorème de Kuratowski

Un multigraphe est planaire si et seulement si il ne contient aucune subdivision du graphe complet K₅ et du graphe biparti K_3,3.
On appelle subdivision d'un graphe tout graphe obtenu en ajoutant des sommets sur les arêtes.

Formule d'Euler

Les arêtes délimitent dans un graphe planaires des faces , y compris la face infinie extèrieure au graphe.
Si un graphe planaire connexe a S sommets F faces et A arêtes, on a la formule :

S + F = A + 2

Graphe dual

Etant donné un graphe planaire G connexe et sans sommets isolés, on peut lui faire correspondre un graphe planaire "dual" G^*.
Chaque face de G correspond un sommet de G^*
Deux sommets de G^* sont reliés si et seulement si les faces correspondantes de G on une arête commune (frontière).

Théorème des quatre couleurs

Ce théorème, démontré en 1976, affirme que pour colorier les faces d'un graphe planaire (les pays d'une carte géographique), il suffit de quatre couleurs.
Ceci revient à colorier les sommet du graphe dual, et donc le théorème équivalent : Tout graphe planaire est 4-coloriable