Graphe de Desargues
# Graphe de Desargues

En théorie des graphes, le graphe de Desargues est un graphe cubique symétrique possédant 20 sommets et 30 arêtes. Il doit son nom à Girard Desargues.

## Construction

Le graphe de Desargues est isomorphe au graphe biparti de Kneser $H_{5,2}$ et au graphe généralisé de Petersen GP(10,3). C'est aussi le graphe d'incidence de la configuration de Desargues.

Le graphe de Desargues est hamiltonien et peut être décrit par la notation LCF : [5, −5, 9, $−9]^5.$

## Propriétés

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

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

Le graphe de Desargues n'est pas planaire. En fait pour le dessiner sur un plan il faut nécessairement que plusieurs arêtes se croisent. Il est possible de le dessiner avec seulement 6 croisements et ce nombre est minimal. Avec ses 20 sommets, il est le plus petit graphe cubique nécessitant 6 croisements pour être dessiné sur le plan.

### Coloration

Le nombre chromatique du graphe de Desargues est 2. C'est-à-dire qu'il est possible de le colorer avec 2 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 1-coloration valide du graphe.

L'indice chromatique du graphe de Desargues est 3. Il existe donc une 3-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.

### Propriétés algébriques

Le graphe de Desargues est symétrique, c'est-à-dire que son groupe d'automorphismes agit transitivement sur ses arêtes, ses sommets et ses arcs. Son groupe d'automorphisme est d'ordre 240 et est isomorphe à $S_5×$ Z/2Z, le produit direct du groupe symétrique $S_5$ avec l'unique groupe d'ordre 2. Seuls deux graphes cubiques symétriques à 20 sommets existent et 20 est le plus petit ordre où il existe deux graphes cubiques symétriques distincts : F20A et F20B selon la notation du Foster Census. F20A est le graphe dodécaédrique, F20B est le graphe de Desargues. Aux ordres 4, 6, 8, 10, 14, 16 et 18 il n'existe qu'un seul graphe cubique symétrique.

Le polynôme caractéristique de la matrice d'adjacence du graphe de Desargues est : $(x-3)(x-2)^{4}(x-1)^{5}(x+1)^{5}(x+2)^{4}(x+3)$. Le graphe de Desargues est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

## Galerie

* Le graphe de Desargues coloré de façon à mettre en valeur certains cycles.
* Les arêtes du graphe de Desargues peuvent être colorées avec 3 couleurs.
* Le nombre chromatique du graphe de Desargues est 2.
