title: Graphe distance-unité
text: # Graphe distance-unité
  
  En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'un ensemble de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette.
  
  ## Exemples
  
  * Tous les cycles et toutes les grilles ;
  * N'importe quel hypercube, donc le graphe hexaédrique et le graphe tesseract ;
  * Le graphe de Petersen ainsi que celui de Moser, de Harborth et de Golomb ;
  * Le graphe roue $W_7$ (c'est le seul graphe roue à être distance-unité) ;
  * Le graphe papillon, le graphe longhorn, le graphe diamant, le graphe taureau, le graphe griffe, le graphe criquet, le graphe poisson, le graphe fléchette, le graphe fourche, le graphe cerf-volant, le graphe croix et le graphe mite.
  
  ## Dénombrement
  
  Paul Erdős posa le problème suivant en 1946 : étant donnés n points, comment estimer le nombre maximal de paires de points pouvant être à une distance de 1 sur le plan euclidien ? En d'autres termes quelle est la densité maximale d'un graphe distance-unité d'ordre n ? Ce problème est très lié au théorème de Szemerédi-Trotter.
  
  L'hypercube fournit une borne inférieure sur le nombre de paires de points proportionnelle à n log n.
  
  ## Application
  
  Le problème de Hadwiger-Nelson, introduit en 1944 par Hugo Hadwiger et Edward Nelson, concerne le nombre minimal de couleurs qu'il faut pour colorier le plan de façon que deux points à une distance de 1 ne soient jamais de la même couleur. Il peut être formalisé en théorie des graphes de la façon suivante : quel est le nombre chromatique maximal d'un graphe distance-unité ? Le problème est toujours ouvert mais le graphe de Golomb, avec son nombre chromatique égal à 4, fournit une borne inférieure. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser. Cependant, cette borne a été améliorée en 2018 grâce à la découverte d'un graphe distance-unité de nombre chromatique 5.
  
  ## Généralisation
  
  La notion de dimension d'un graphe reprend l'idée d'un graphe tracé avec des arêtes de longueur 1, mais ne se restreint pas au plan.
  
  