Open Manage | Database | Relationships
Check every relationship between contacts and company (I'm guessing that these are the table names) by double clicking relationship lines.
Look for relationships where a "delete" option has been selected. Given that the boxes in your relationship graph can have multiple occurrences of these two tables, you may need to check multiple relationships to find the culprit.
Here's what I think is happening:
You have two cases where you've specified this "delete" option. It could be in the same relationship or two different relationships.
This option deletes all matching records in a related table when a record is deleted in the first table.
Thus, this delete option is deleting the matching company record when you delete a contact. But then, if you have a second delete option enabled for contacts when a company record is deleted, deleting that company record deletes all the matching contacts records--which produces the results you have experienced. If this is the case, clear the delete option for deleting company records when a contact is deleted and this won't happen. You can keep the other delete option or not at your option.
The other possibility is that you only have the delete option for deleting matching contacts when the company record is deleted, but your delete action actually deleted a company record. This would also produce the results you experienced here.