graphe de Petersen

Prenez cinq nombres distincts et écrivez toutes les paires possibles : il y en a dix. Chaque paire devient un point. Reliez deux points seulement lorsque leurs paires n'ont aucun nombre en commun.

Le réseau obtenu est le graphe de Petersen. De chaque point partent exactement trois arêtes. Pourtant, trois couleurs ne suffisent pas pour colorier ses arêtes sans donner la même couleur à deux arêtes qui se rencontrent. Cette petite structure sert ainsi de contre-exemple à des affirmations trop générales.

Le graphe de Petersen est un graphe simple à dix sommets et quinze arêtes. Chaque sommet possède exactement trois voisins : le graphe est donc cubique, ou 3-régulier. Il est sans isthme, car la suppression d'une seule arête ne le déconnecte pas. Il est aussi non planaire : aucun tracé dans le plan ne peut représenter toutes ses adjacences sans croisement.

Une définition complète l'identifie au graphe de Kneser KG(5, 2). On part d'un ensemble de cinq éléments. Les sommets sont ses sous-ensembles de deux éléments, autrement dit ses dix paires. Deux sommets sont adjacents exactement lorsque les deux paires sont disjointes. Pour une paire donnée, les trois éléments restants forment trois autres paires ; le degré vaut donc 3. La somme des dix degrés vaut 30 et compte chaque arête deux fois, d'où 15 arêtes.

Malgré sa régularité et l'absence d'isthme, le graphe de Petersen n'est pas 3-arête-colorable : au moins quatre couleurs sont nécessaires pour que deux arêtes ayant une extrémité commune aient des couleurs différentes. Il est isomorphe au squelette du hémi-dodécaèdre, c'est-à-dire qu'il possède la même structure d'adjacence.

La construction KG(5, 2) repose sur quatre éléments liés. Un ensemble de cinq éléments fournit les données de départ. Ses dix paires deviennent les sommets. La disjonction fournit la règle d'adjacence : deux paires sans élément commun déterminent une arête. Les quinze arêtes ainsi obtenues donnent trois voisines à chaque paire.

Les sommets dépendent donc du choix des paires, tandis que les arêtes dépendent de leur disjonction. Ces deux règles suffisent à reconstruire tout le graphe et à calculer ses degrés. En revanche, la position des points, la longueur des traits, leur couleur ou la forme pentagonale souvent choisie ne définissent pas l'objet. Deux dessins très différents représentent le même graphe s'ils conservent exactement les mêmes adjacences.

Construisons le graphe à partir de l'ensemble {1, 2, 3, 4, 5}. Les données sont les cinq éléments, les paires de deux éléments et la règle « relier deux paires disjointes ».

1. Énumérez les paires : 12, 13, 14, 15, 23, 24, 25, 34, 35 et 45. Elles donnent dix sommets.
2. Partez du sommet 12. Les éléments restants sont 3, 4 et 5 ; ses voisines sont donc 34, 35 et 45.
3. Répétez cette règle pour chaque sommet. Chaque paire laisse trois éléments, qui fournissent exactement trois paires disjointes.
4. Additionnez les degrés : 10 × 3 = 30. Chaque arête étant comptée à ses deux extrémités, le graphe possède 30 ÷ 2 = 15 arêtes.

Le dessin associé montre ces dix sommets, leurs quinze arêtes et les trois arêtes issues de chacun. Pour contrôler la construction, choisissez une paire quelconque : ses trois voisines doivent être exactement les trois paires formées avec les éléments qu'elle ne contient pas.

Pour tester une affirmation sur tous les graphes cubiques sans isthme, on examine le graphe de Petersen en premier. Si l'affirmation lui impose une coloration des arêtes avec trois couleurs, ce graphe fournit immédiatement un contre-exemple.

Pour reconstruire l'objet sans dépendre d'un dessin, on utilise la forme KG(5, 2). Il suffit d'énumérer les dix paires, puis de relier les paires disjointes. Cette description est préférable au pentagone étoilé dès qu'il faut vérifier une adjacence plutôt que reconnaître une silhouette.

Pour étudier la planarité, un dessin particulier ne suffit pas. Le critère pertinent porte sur l'existence d'un tracé sans aucun croisement ; pour le graphe de Petersen, un tel tracé n'existe pas.

Trois expressions proches décrivent ici des propriétés différentes. Pour les séparer, il faut regarder ce que chacune mesure.

Un dessin qui présente des croisements peut parfois être redessiné sans croisements. Un graphe non planaire, lui, ne possède aucun tracé plan sans croisement. Le graphe de Petersen relève du second cas, pas seulement d'une représentation maladroite.

« 3-régulier » décrit le nombre d'arêtes incidentes à chaque sommet. « 3-arête-colorable » décrit la possibilité de colorier les arêtes avec trois couleurs sans conflit à une extrémité. Le graphe de Petersen vérifie la première propriété, mais pas la seconde.

La qualification de « plus petit » ne vaut pas sans toutes les conditions annoncées : graphe cubique, sans isthme et non 3-arête-colorable. Si l'une d'elles disparaît, la comparaison ne porte plus sur la même classe de graphes. Il faut donc rétablir les trois critères avant d'utiliser cette propriété minimale.

Le pentagone et l'étoile constituent un dessin commode, pas une définition. Déplacer les sommets ou ajouter des croisements visuels ne change pas le graphe tant que les quinze adjacences restent identiques. Pour trancher, il faut comparer les paires de sommets reliées.

L'absence d'isthme concerne la suppression d'une seule arête. Elle n'autorise pas à conclure qu'une suppression quelconque laisse toujours le graphe connexe. Le bon contrôle consiste à retirer une arête à la fois et à vérifier qu'un chemin subsiste entre tous les sommets.

La notion de graphe planaire précise ce que signifie l'existence d'un dessin sans croisement et permet de situer exactement la non-planarité du graphe de Petersen.