When I installed telegram, I was astonished to see the contacts which I had deleted long before. I wonder how they are still in my phone or still attched to my google contacts. What happens when we delete a contact from android phone? will it be deleted forever of google just hides it?
It depend where you delete the contact from. There are local copies and copies on your Google account, you have to delete it from both places, because if sync is enabled it will automatically re-add them. But if you did delete it from both places, but it could be an error (Things like this do happen sometimes).
Additional Info: if you had another device with the same Google account on it, and edited your contacts then Google automatically keeps the latest record of your contact book and saves the latest version of it. Hope this helps