La notion d'ensemble indépendant est liée à un graphe (non orienté). On prendra pour exemple le graphe de Moser :
Un ensemble indépendant (ou « stable ») du graphe, est un ensemble de sommets tel qu'aucun de ces sommets ne soit adjacent à un autre sommet du même graphe.
En prenant tous les sommets du graphe de Moser, l'ensemble obtenu n'est pas indépendant :
Même celui-là ne l'est pas : les deux sommets sont adjacents.
Cet ensemble est évidemment indépendant, puisqu'il n'y a qu'un sommet dedans :
Il est possible d'obtenir un ensemble indépendant de 2 sommets dans le graphe de Moser :
La règle du jeu consiste donc à placer le plus de pions possible sur un graphe de manière qu'il n'y ait aucune arête entre deux pions (aucun pion ne doit gêner le mouvement d'un autre pion).
Sur ce graphe, quelle est la taille du plus grand ensemble indépendant ?
On peut faire au moins 8 :
Peut-on faire mieux ?
Quelle est la taille maximale d'un ensemble indépendant sur le graphe de Herschel ?
On peut faire au moins 6 :
Montrer qu'on ne peut pas faire mieux.
Quelle est la taille du plus grand ensemble indépendant sur ce graphe ?