Mi rispondo da solo: ho provato a dichiarare v, all'interno della funzione AddAdj, come un puntatore a un vertice:
Vertice* v=new Vertice;
v->Ver=b;
v->Next=Adj[a];
Adj[a]=v;
E adesso tutto funziona bene. Solo non capisco, come mai i puntatori creati internamente si conservano, mentre se non sono puntatotori no.