1. If it is just a few contacts that are posing this error then I would just open the records and delete the associated records. Set the relationship to display if it is not already showing associated records.
2. Change the relationship behavior from restrict delete temporarily and then delete the records. This wouldn't be an good option if there are a lot of such relationships!
3. Alternatively deactivate the contact record.
If my response helps you in finding your answer then please click 'Mark as Answer' and 'Vote as Helpful'