Empezaremos con un

Ejemplo:
Dado un mapa de las autopistas de un lugar, se podría determinar si existe una ruta por autopista entre dos ciudades en el mapa. Sea S = {a, b, c, ...} el conjunto de ciudades y una relación binaria sobre S tal que (a, b) si existe una autopista de la ciudad a a la ciudad b.

= {(a, b), (a, c), (a, d), (a, e), (b, d), (c, d), (d, e)}

Los vértices, que son los puntos del grafo, representan los elementos del conjunto. Los lados representan los elementos (x, y) que están relacionados.