Un graphe simple est un graphe n'ayant pas de multi-arête (plusieurs arêtes différentes avec les mêmes extrémités).
Un tel graphe est parfois utile lorsque l'application manipule des
relations simples entre les sommets. Un exemple d'une telle
application peut être le réseau d'une ligne aérienne. Pour
déterminer comment aller d'un aéroport à un aéroport
, il
suffit de savoir si deux aéroports sont reliés par une route directe.
Parfois, on exige pour qu'un graphe soit simple, l'absence de boucles.