If you really want to use Deleted, you'd have to make your foreign keys nullable, but then you'd end up with orphaned records (which is one of the main reasons you shouldn't be doing that in the first place). So just use Remove()
ObjectContext.DeleteObject(entity) marks the entity as Deleted in the context. (It's EntityState is Deleted after that.) If you call SaveChanges afterwards EF sends a SQL DELETE statement to the database. If no referential constraints in the database are violated the entity will be deleted, otherwise an exception is thrown.
EntityCollection.Remove(childEntity) marks the relationship between parent and childEntity as Deleted. If the childEntity itself is deleted from the database and what exactly happens when you call SaveChanges depends on the kind of relationship between the two:
A thing worth noting is that setting .State = EntityState.Deleted
does not trigger automatically detected change. (archive)