Is it possible to verify if a post has been deleted using Graph API?
By what information you've given. I would suggest you look at this doc for info. https://developers.facebook.com/docs/graph-api/reference/v2.9/post/
It has some variables like "is_published", "is_visible" and other.
So an answer to your question is, maybe and yes.