title: Graphes de Behrend
text: # Graphes de Behrend
  
  Les graphes de Behrend sont des graphes ayant la propriété suivante : toutes leurs arêtes appartiennent à un et un seul triangle. Ils sont basés sur les ensembles d'entiers ne contenant aucune progression arithmétique.
  
  ## Définition
  
  Soit [m] l'ensemble des entiers de 1 à m. Soit X un sous-ensemble de [m] ne contenant pas trois nombres en progression arithmétique. Autrement dit, pour tout i,j,k distincts dans X, on ne peut avoir j-i = k-j (autrement formulé, on ne peut avoir i+k=2j.)
  
  On définit alors le graphe suivant :
  
  * Il contient 6m sommets.
  * Ces sommets sont répartis en trois ensemble de respectivement m,2m et 3m sommets, que nous noterons $V_1,V_2$ et $V_3,$ et numérotés respectivement de 1 à m, de 1 à 2m et de 1 à 3m.
  * Pour tous sommets de x de $V_1$ et y de $V_2,$ il y a une arête de x à y si et seulement si y-x est dans X. De même entre les sommets de $V_2$ et ceux de $V_3.$ Entre un sommet x de $V_1$ et un sommet z de $V_3,$ il y a une arête si et seulement si z-x est dans X.
  
  Le graphe a alors les propriétés suivantes :
  
  * Il contient 3|X|m arêtes
  * Il contient |X|m triangles
  * Chaque arête appartient à un et un seul triangle.
  