title: Graphe d'intervalles propre
text: # 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.
  
  