Un Graphe sera dit planaire s'il admet une représentation sagittale planaire, c'est à dire une représentation dans le plan où les sommets du graphe sont des points du plan et les arcs des courbes simples ne se rencontrant qu'en un sommet.

Attention : pour qu'un graphe soit planaire, il faut qu'il admette au moins une représentation planaire, pas que toutes le soient.

 

K4 est-il planaire ?
Si on se fonde sur sa représentation sagittale classique ci-contre, il semblerait que non.
Pourtant, on pourrait représenter le graphe autrement, en faisant passer l'arc 2,4 par l'extérieur, on aurait alors une représentation planaire.

 

K4 est donc bien un graphe planaire.

Dans la représentation planaire d'un graphe, on appellera face tout région du plan non traversée par des arcs.

Dans l'exemple ci-dessus, il y a 6 faces (n'oubliez pas la face infinie), 12 sommets et 16 arcs.

 

Propriété 1 : Dans un graphe planaire d'ordre n avec m arcs, on a : f = m - n + 2. Cette formule s'appelle Formule d'Euler.

 

Démonstration : par récurrence sur m,
C'est vrai pour le graphe contenant 2 sommets et un arc : f=1, n=2, m=1 d'où : f-m+n= 2
Quand on rajoute un arc, deux cas de figure peuvent se présenter : soit on rajoute un sommet dans une face et le nombre de faces ne change pas; soit on ne rajoute pas de sommet, l'arc ajouté arrive donc sur un sommet déjà existant, mais alors, on a coupé une face en 2, donc ajouté une face.
Dans tous les cas, le nombre f-m+n ne varie pas, reste donc égal à 2.

 

Propriété 2 : K5 n'est pas planaire

 

Démonstration : S'il était planaire, sa représentation planaire comporterait (d'après la Formule d'Euler) 10-5+2 = 7 faces.
Or, il faut au moins 3 arcs pour fermer une face et un arc pouvant servir de frontière à 2 faces, avec 10 arcs, il ne peut y avoir plus de 20/3 faces, d'où une contradiction

 

Propriété 3 : K3,3 n'est pas planaire

 

Démonstration : S'il était planaire, sa représentation planaire comporterait (d'après la Formule d'Euler) 9-6+2 = 5 faces.
Or, il faut au moins 4 arcs (dans le cas d'un graphe biparti, on ne peut pas fermer une face avec un nombre impair d'arcs!) pour fermer une face et un arc pouvant servir de fontière à 2 faces, avec 9 arcs, il ne peut y avoir plus de18/4 faces, d'où une contradiction.

 

 

Il existe une réciproque à ces deux propriétés, connue sous le nom de Théorème de Kuratowski, dont la démonstration est assez difficile.

 

TH de Kuratowski : Les seuls graphes non planaires sont ceux admettant K5 ou K3,3 comme sous-graphes.

 

 

 

EXERCICE D'APPLICATION CONCRETE : Combien y a-t-il de pentagones et d'hexagones sur un ballon de football ?


CORRECTION

 

EXERCICES