Further to Pradeep Nayak's reply, the ultimate cause of the problems I was having were missing foreign key constraints on the civicrm_relationship table leaving orphaned data when contacts were deleted.
Therefore, a solution which fixes the problem rather than working around it would be:
Check that all foreign key constraints are missing on ...
Your system have orphan data in civicrm_relationship table. There are few rows in civicrm_relationship table that have contact id in column civicrm_relationship.contact_id_a or civicrm_relationship_contact_id_b are missing in civicrm_contact.
FROM civicrm_relationship cr
LEFT JOIN civicrm_contact cc
ON cc.id = cr.contact_id_a
WHERE cc.id IS ...
Welcome to SE! Yes, you can import the relationship at the same time. The documentation describes your situation here.
This is based on one row per child with parent details in the columns. You import once for child, mother, relationship and once for child, father, relationship.
Check that your default dedupe rules work for the parent fields you are ...