Graphe de Desargues

Le graphe de Desargues est isomorphe au graphe biparti de Kneser ${\displaystyle 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]⁵.

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