title: Problème de réalisation de graphe
text: # Problème de réalisation de graphe
  
  Le problème de réalisation de graphe est un problème algorithmique. Étant donné une liste de nombres entiers, il consiste à décider s'il existe un graphe dont la liste des degrés est égale à la liste donnée en entrée.
  
  ## Définition
  
  On dit qu'un graphe non orienté réalise une certaine liste de nombres entiers, si la suite des degrés de graphe est égale à la liste en question.
  
  Le problème de réalisation d'un graphe consiste, étant donné une liste, à décider s'il existe un graphe qui réalise cette liste.
  
  ## Algorithmes et propriétés
  
  L'algorithme de Havel-Hakimi résout le problème en temps $polynomial^,.$
  
  Le théorème d'Erdős-Gallai (en) donne une caractérisation des suites qui sont réalisables.
  
  