Have just discovered ( and confirmed on https://wpmaster.demo.civicrm.org ) that Relationships of a deleted Contact are continue to be active and are displayed as such.
Not quite sure if it is a bug or a feature? Why would Relationships with deleted Contacts be kept active? Shouldn't the system at least disable them?