After software update phone erased

Yes, since Contacts are stored by your email provider on their servers, so when you set up email again, the Contacts were synced back to your iPhone.

Stated another way, your email provider "backs up" Contacts on their servers, so while the phone was erased, the Contacts remained on the email servers of your provider.

Back ups should be routinely made because of things like this.

Yes, your data is gone.

Yes, contacts are tied to your email provider so you should be able to log back into your account with them.