Un grafo se define como un par ordenado donde
- es un conjunto finito de puntos llamados vértices o nodos, y
- es un conjunto de pares no ordenados de elementos distintos de cuyos elementos son llamados aristas o enlaces.
Se dice que dos vertices son adyacentes si .
Un grafo simple se refiere a un grafo que no tiene bucles, i.e. aristas adyacentes a sí mismas, ni aristas multiples, i.e. no hay más de una arista que conecte el mismo par de vértices.
Dado que hay pares únicos de vértices en un conjunto de vértices , y cada par puede tener una arista o no, hay configuraciones posibles. I.e. el número de grafos simples distintos para es