On considère un graphe (non orienté), par exemple le graphe de Moser :
Un ensemble de sommet couvre le graphe si chaque arête du graphe est adjacente à au moins un des sommets. Un exemple simple est celui consistant à poser des pions sur tous les sommets :
Mais le but du jeu est d'en placer le moins possible. En enlevant un pion superflu, on conserve un ensemble couvrant :
Mais on peut faire mieux :
Le graphe de Moser peut donc être couvert par seulement 5 pions. Peut-on le couvrir avec moins de 5 pions ?
Sur ce graphe, quelle est la taille du plus petit ensemble couvrant ?
Cet ensemble de 8 sommets est couvrant :
Peut-on faire mieux ?
Quelle est la taille minimale d'un ensemble couvrant sur le graphe de Herschel ?
5 pions suffisent :
Montrer qu'on ne peut pas faire mieux.
Quelle est la taille du plus petit ensemble couvrant sur ce graphe ?