Graphe complémentaire
# 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 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.
