How to delete all objects through a core data relationship?

Setting the department's employee relationship to an empty set WILL NOT delete the employees, regardless of the deletion rule. I believe you are misunderstanding the deletion rule. According the apple docs: "A relationship's delete rule specifies what should happen if an attempt is made to delete the source object". Thus, cascading will only take effect if we DELETE the department. By setting the relationship to an empty set, all we are doing is separating the employees from the department, not deleting them. And if that relationship is not set to optional for the employees, this will cause an error when saving. If you want to delete the employees from the department, you can iterate through them as listed above, or set the department relationship to cascade and then delete the department.

If you want to delete the employee elements for a specific department, then you could run a for-in loop like for

for (Employees * theEmployee in department.employees) {
  [self.managedObjectContext deleteObject:[self.managedObjectContext objectWithID:theEmployee.objectID]]; 
}

Then save your managed context. IF of course that's what you want, and not remove the relationship between employees and departement; in that case, assigning an empty set would work.

Variation on above:

for (Employee *employeeToDelete in department.employees) {
    [self.managedObjectContext deleteObject:employeeToDelete];
}

I also had something like below but it didn't work...

- (BOOL)deleteCollection:(Collection *)collection {
    // Grab the context
    NSManagedObjectContext *context = [self managedObjectContext];
    NSError *error = nil;

    [collection removeSounds:collection.sounds];
    [context deleteObject:collection];

    // Save everything
    if ([context save:&error]) {
        return YES;
    }
    return NO;
}

Obviously the database layer can't delete the sounds and then the collection at once. Setting the delete rule on the relationship to 'cascade' nicely solved my problem and let me use just:

[context deleteObject:collection];

If you want to save some people detailed reading time then just mark this as the answer.

As Fervus stated above, this link may also be helpful for the pros: Propagate deletes immediately in Core Data