Soit un graphe non orienté fini. Un graphe est un mineur de si peut être obtenu à partir de en effectuant un nombre quelconque d'opérations parmi les suivantes :
suppression d'un sommet isolé : le sommet est supprimé du graphe ;
suppression d'une arête : on supprime l'arête , mais ses extrémités restent inchangées ;
contraction d'une arête : on supprime l'arête , les deux sommets et sont fusionnés en un sommet . Toute arête ou est remplacée par une nouvelle arête . Une même arête n'est pas ajoutée deux fois (on ne crée pas d'arêtes parallèles).
Cette définition est celle qui est donnée par László Lovász[1]. On trouve des définitions différentes, mais équivalentes, dans la littérature. Une autre définition est la suivante. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .
Exemple
Dans cet exemple, le graphe est un mineur de :
:
:
Pour le voir, considérons le diagramme suivant qui montre les opérations à effectuer sur pour arriver à :
on supprime les arêtes en pointillé
on supprime le sommet isolé (tout à droite)
on contracte l'arête en gris.
Utilité
Une des utilités du concept de mineur est la caractérisation de classes de graphes particulières comme ayant (ou n'ayant pas) un certain graphe comme mineur. Par exemple, un graphe planaire ne contient comme mineur ni (graphe complet d'ordre 5), ni (graphe biparti complet d'ordre 3). Le théorème de Robertson-Seymour montre que l'on peut caractériser ainsi tous les graphes qui peuvent être tracés sur une surface donnée, en fonction d'un ensemble de mineurs exclus. La notion de mineur permet également d'exprimer simplement certains théorèmes ou conjectures, comme la conjecture de Hadwiger selon laquelle tout graphe dont le graphe complet à sommets n'est pas un mineur est colorable avec couleurs.
