You should have a rountine that dereference this entity from its related entities, and then remove it from the main collection.
You don't have to prase the graph for references of this entity, it's enough to just use that entity's related collections/navigators and de-reference them, this should automatically de-reference the entity from these related entities' collections/navigators.
P.S. r to use a context to guarantee unique instances of each entity.