title: Graphe de Perkel
text: # Graphe de Perkel
  
  Le graphe de Perkel est, en théorie des graphes, un graphe 6-régulier possédant 57 sommets et 171 arêtes. C'est l'unique graphe distance-régulier ayant pour vecteur d'intersection {6, 5, 2 ; 1, 1, 3}.
  
  ## Construction
  
  Les sommets du graphe de Perkel peuvent être définis comme les éléments du groupe abélien Z/3ZxZ/19Z où (i,j) est relié à (i+1,k) si $(k-j)^3$ = $2^{6i}.$
  
  ## Propriétés
  
  ### Propriétés générales
  
  Le diamètre du graphe de Perkel, l'excentricité maximale de ses sommets, est 3, son rayon, l'excentricité minimale de ses sommets, est 3 et sa maille, la longueur de son plus court cycle, est 5. Il s'agit d'un graphe 6-sommet-connexe et d'un graphe 6-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre non connexe il faut le priver au minimum de 6 sommets ou de 6 arêtes.
  
  ### Coloration
  
  Le nombre chromatique du graphe de Perkel est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes et que ce nombre est minimal. Il n'existe pas de 2-coloration valide du graphe.
  
  ### Propriétés algébriques
  
  Le groupe d'automorphismes du graphe de Perkel est d'ordre 3 420.
  
  Le polynôme caractéristique de la matrice d'adjacence du graphe de Perkel est : $-(x-6)(x+3)^{20}(x^{2}-3x+1)^{18}$.
  
  