Feels like a schema design issue?
If your REST backend exposes a single path to remove an item, are there any reason why your GraphQL schema doesn't expose a root mutation field taking the same arguments?
We are paying that same complexity tax you described, but without the benefit of needing to support thousands of unknown 3rd-party developers.
Equivalent delete queries in rest / graphql would be
curl -X DELETE 'https://api.example.com/users/123'
curl 'https://api.example.com/graphql?query={ deleteUser(id: 123) { id } }'