Graphe dans lequel deux sommets quelconques sont reliés par au moins une arête.
- On peut dire qu’un graphe complet est un graphe simple dont tous les sommets sont adjacents, c’est-à-dire que tout couple de sommets est relié par une arête.
- On dit aussi qu’un graphe complet est un graphe simple dans lequel toutes les arêtes possibles apparaissent.
Exemple
Le graphe ci-dessous est un graphe complet, car chacun des sommets est relié à chacun des autres sommets du graphe :
