Recientemente tuve que modelar árboles y listas en Modula-2, así que tengo el tema de los TDA bastante fresco
Yo lo haría simplemente con una clase vértice que contenga una lista (llámala "aristas" si quieres) de otros vértices. De esta forma un grafo sería un conjunto de vértices, creo que haciendo una clase Grafo cuyos objetos contengan una lista de vértices sería suficiente
Saludos.