Graphe d'intervalles propre
# Graphe d'intervalles propre

Un graphe d'intervalles propre est un graphe d'intervalles possédant une représentation d'intervalles dans laquelle aucun intervalle n'est inclus dans l'autre.

## Propriétés

Un graphe d'intervalles propre est nécessairement un graphe sans griffe.

### Démonstration

Soit $G$ un graphe possédant une griffe comme sous-graphe induit. On appelle $A,B,C,D$ les quatre sommets de la griffe d'intervalles respectives $I_{a}=[a_{1};a_{2}]$,$I_{b}=[b_{1};b_{2}]$,$Ic=[c_{1};c_{2}]$ et $I_{d}=[d_{1};d_{2}]$ tels que le sommet $D$ soit celui relié aux trois autres et que $a_{1}\leq b_{1}\leq c_{1}$.

Comme la griffe est un graphe induit, $A$, $B$ et $C$ ne sont pas voisins dans $G$. On a donc $a_{1}\leq a_{2}\leq b_{1}\leq b_{2}\leq c_{1}\leq c_{2}$.

$D$ est voisin de $A$ et $C$ donc $I_{a}\cap I_{d}\not =\emptyset$ et $I_{c}\cap I_{d}\not =\emptyset$ d'où $d_{1}\leq a_{2}$ et $c_{1}\leq d_{2}$. On a donc $d_{1}\leq a_{2}\leq b_{1}\leq b2\leq c_{1}\leq d_{2}$, d'où $I_{b}\subset I_{d}$. $G$ n'est donc pas un graphe d'intervalle propre.

