Gli oggetti ancora referenziati da un puntatore non vengono eliminati. E comunque anche se non fossero piu' referenziati non è detto che vengano eliminati subito, dipende dal garbage collector.
Quindi la tua prima soluzione non funziona visto che anche se setti il puntatore iniziale a null, c'è l'hashmap che si tiene l'oggetto (ovviamente non è una copia ma è lo stesso che è stato rilasciato dal tuo puntatore) quindi non verra' cancellato...
O rivedi il codice oppure il max che puoi fare e' scrivere un codice che elimini il Grafo dalle HashMap dove sono referenziate per dereferenziarle e sperare che il garbage collector li elimini.