Hola Ignacio. Habían varias versiones de este ejercicio (que esencialmente se resuelven de la misma forma) y según lo que decís te debe haber tocado el grafo cuyos vértices son secuencias binarias de largo 6, donde dos vértices adyacentes corresponde a secuencias binarias que difieren en dos posiciones.
Es verdad que existen 64 secuencias binarias diferentes, pero la condición de adyacencia define una única relación (no entiendo a que te refieres con cuántas relaciones de esas puede haber).
Para obtener la cantidad de aristas la forma más sencilla es observar que cada vértice está conectado con exactamente C(6,2)=15 otros vértices (i.e. todo vértice tiene grado 15) - eso es porque un vértice es una lista con 6 coordenadas y hay C(6,2) pares de coordenadas posibles. Sumando eso para todos los vértices te da 15 x 64. En esa suma estás contando cada arista dos veces por lo que el resultado es 15*32=480 (es equivalente a aplicar la fórmula que dice que la suma de los grados de los vértices es el doble que la cantidad de aristas).