Graphe complémentaire

En théorie des graphes, le graphe complémentaire ou graphe inversé d'un graphe simple $G$ est un graphe simple $H$ ayant les mêmes sommets et tel que deux sommets distincts de $H$ soient adjacents si et seulement s'ils ne sont pas adjacents dans $G$.

Le graphe de Petersen, à gauche et son complémentaire, à droite.

Le graphe complémentaire ne doit pas être confondu avec le complémentaire dans le sens de la théorie des ensembles. En effet, l'ensemble des sommets de G reste inchangé.

Propriétés

• Le complémentaire du complémentaire est le graphe original.
• La somme d'un graphe et de son complémentaire est le graphe complet.
• Une clique dans un graphe est un ensemble indépendant dans son graphe complémentaire.
• Les graphes auto-complémentaires sont les graphes qui sont isomorphes à leur complémentaire.
• Les cographes sont définis notamment par une opération de complémentation.