Graphes de Behrend
# 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.
