Un grafo es un conjunto de objetos llamados nodos o vértices, que pueden estar unidos (conectados) por líneas llamada aristas.

En la imagen anterior vemos una grafo con 6 vértices (numerados desde el 1 hasta el 6). También vemos algunas aristas que unen (o conectan) parejas de vértices.
Por ejemplo: el vértice 1 está conectado con los vértices 2 y 5, pero no está conectado con el resto de vértices.

En los grafos de tipo «simple», no puede haber más de una arista que una dos vértices cualesquiera