Exercice 2 - K-COLORATION/ENSEMBLE STABLE

Soit $G = (S, A)$ un graphe, $k$ une constante strictement positive. On s'intéresse à la $k$-colorabilité du graphe $G$ (i.e. peut-on colorier le graphe $G$ avec $k$ couleurs ?). Nous allons créer un graphe $G^\prime = (S^\prime, A^\prime)$ à partir de $G$ en procédant de la façon suivante :

• A chaque sommet $s$ de $G$, on associe $k$ sommets de $G^\prime$, notés $\{(s, 1), \ldots, (s, k)\}$, tous reliés entre eux par des arêtes.
• Pour chaque arête $\{e, e^\prime\}$ de $G$, et chaque couleur $j$, on relie dans $G^\prime$ les sommets $(e, j)$ et $(e^\prime, j)$. Notez bien que comme les sommets sont des couples, les arêtes sont des paires de couples.

Plus formellement,

• 
  
  $$S^\prime = \{(s, j) \vert s \in S, j \in \{1, \ldots, k\}\}$$
  
  
  est un ensemble de couples (sommet de $G$/couleur).
• 
  
  $$A^\prime = A_1 \cup A_2$$
  
  
  avec
  
  $$A_1 = \{\{(s, j), (s, j^\prime)\} \vert s \in S, 1 \leq j < j^\prime \leq k\}$$
  
  
  un ensemble d'arêtes formant $\vert S\vert$ sous-graphes complets de $k$ sommets et
  
  $$A_2 = \{ \{(e, j), (e^\prime, j)\} \vert \{e, e^\prime\} \in A, j \in \{1, \ldots, k \}\}$$
  
  
  un ensemble d'arêtes reliant ces sous-graphes.

Démontrez de façon formelle et avec le plus de rigueur possible que, étant donné un graphe $G$ arbitraire, un nombre $k > 0$, $G$ est $k$-colorable si et seulement s'il existe un ensemble stable de $\vert S\vert$ sommets dans $G^\prime$.