Hai ragione, non so perchè non mi desse gli errori, ti ringrazio!
Quindi ecco qui il risultato corretto però comunque fa le bizze e non so se è un problema del mio compilatore (come per gli errori) o se ho fatto proprio un errore di logica:
codice:
void deleteArco(EDGELIST* t, NODE x, NODE y){
    if ((*t) != NULL) { 
        if( (*t)->nodo1 == x && (*t)->nodo2 == y){
            EDGELIST p = (*t);
            (*t) = (*t)->next;
            free(p);
        }else
            deleteArco(&(*t)->next, x, y);
    }
}
Comunque grazie ancora @scara95