Graphe de Clebsch
# Graphe de Clebsch

Le graphe de Clebsch est, en théorie des graphes, un graphe 5-régulier possédant 16 sommets et 40 arêtes. Il a été nommé ainsi à cause de son lien avec la surface quartique (en) découverte par Alfred Clebsch en 1868. On le connait aussi sous le nom de graphe de Greenwood–Gleason, à cause des travaux de Robert E. Greenwood et Andrew Gleason en 1955.

## Construction

On peut construire le graphe de Clebsch en reliant par huit nouvelles arêtes les sommets opposés d'un hypercube en quatre dimensions (c'est-à-dire les sommets à distance quatre l'un de l'autre).

Une autre construction est de fusionner les sommets opposés de l'hypercube en cinq dimensions (donc les sommets à une distance cinq l'un de l'autre).

La construction historique est la suivante :

* on représente les 16 droites contenues dans la quartique de Clebsch par 16 sommets d'un graphe ;
* on relie deux de ces sommets si et seulement si les droites correspondantes ne sont ni parallèles ni sécantes.

On obtient également le graphe de Clebsch en représentant les éléments du corps fini GF(16) par des sommets, et en les reliant lorsque leur différence dans GF(16) est un nombre cubique.

## Propriétés

### Propriétés générales

Le graphe de Clebsch est un graphe fortement régulier de paramètres $(v,k,\lambda ,\mu )=(16,5,0,2)$$^,.$

Le diamètre du graphe de Clebsch, l'excentricité maximale de ses sommets, est 2, son rayon, l'excentricité minimale de ses sommets, est 2 et sa maille, la longueur de son plus court cycle, est 4, c'est donc un graphe sans triangle. Il s'agit d'un graphe 5-sommet-connexe et d'un graphe 5-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 5 sommets ou de 5 arêtes.

Le graphe de Clebsch est également un graphe non-planaire, un graphe non-eulérien et un hamiltonien.

### Coloration

Le nombre chromatique du graphe de Clebsch est 4. C'est-à-dire qu'il est possible de le colorer avec 4 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 3-coloration valide du graphe.

L'indice chromatique du graphe de Clebsch est 5. Il existe donc une 5-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

* Le nombre achromatique du graphe de Clebsch est 8.
* Le nombre chromatique du graphe de Clebsch est 4.
* L'indice chromatique du graphe de Clebsch est 5.

### Propriétés algébriques

Le groupe d'automorphismes du graphe de Clebsch est d'ordre 1 920. Il est isomorphe au groupe de Coxeter $D_5.$ Ce groupe d'automorphismes agit transitivement sur l'ensemble des sommets du graphe de Clebsch, faisant de lui un graphe sommet-transitif.

Le polynôme caractéristique de la matrice d'adjacence du graphe de Clebsch est : $(x-5)(x-1)^{10}(x+3)^{5}$. Il n'admet que des racines entières. Le graphe de Clebsch est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

### Graphe complémentaire

Le graphe complémentaire du graphe de Clebsch est un graphe 10-régulier. Il est lui aussi fortement régulier. Il s'agit du graphe demi-hypercube construit à partir de l'hypercube en 5 dimensions (penteract). Pour le construire, on relie les sommets qui sont à une distance 2 dans l'hypercube ; cela donne deux graphes isomorphes dont on ne garde que l'un des deux.

C'est ce graphe 10-régulier, à 16 sommets et à 80 arêtes que certains auteurs comme J. J. Seidel (en 1968) ou Andries Brouwer appellent « graphe de Clebsch $»^,.$ Le graphe décrit par Clebsch un siècle plus tôt, dans son article de 1868, est néanmoins bien le graphe 5-régulier.

### Divers

Soit $v$ un sommet quelconque du graphe de Clebsch. Le sous-graphe induit aux 10 sommets qui ne sont pas des voisins de $v$ est le graphe de Petersen.

