Graphe de Desargues

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^[2]. Avec ses 20 sommets, il est le plus petit graphe cubique nécessitant 6 croisements pour être dessiné sur le plan^[3].

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.

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₅× Z/2Z, le produit direct du groupe symétrique S₅ 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^[4]. 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^[5].

Le polynôme caractéristique de la matrice d'adjacence du graphe de Desargues est : ${\displaystyle (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.

• 
  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.

• Portail des mathématiques