Sous-graphe d’un graphe donné qui comprend toutes les arêtes manquantes pour que ce graphe soit complet.
Exemple
Soit le graphe G ci-dessous qui est un graphe complet :
Si on considère le sous-graphe E de G comprenant les arêtes {AB, AE, BC, CD, DF, EF}, alors le graphe complémentaire de E, noté E’, est le graphe comprenant les sommets {A, B, C, D, E, F} et l’ensemble d’arêtes {AC, AD, AF, BD, BE, BF, CE, CF, DE}.