Remove duplicates from dictionary in a safe and clever way
Your question is very well written. Let me make one requirement even clearer. "Remove duplicate values" means that one value can be assigned to at most one key in the end, as explained in the given examples. 

Your algorithm might return the wrong result. For example, consider the following dictionary.

{ 1, ["A", "B"] } 
{ 2, ["A", "B"] },
{ 3, ["C", "A", "B"] },
{ 4, ["D", "A", "B"] } 
{ 5, ["C", "D", "E", "F"] } 
{ 6, ["C", "D", "E", "F"] },


Your algorithm might proceed to remove value "C" from key 3 followed by removing value "D" from key 4. You can check that each keys still has at least 2 values and each value is still at least assigned to 2 keys. However, you can see that key 1, 2, 3 and 4 have two values in total, "A" and "B". So it is not possible to assign each of those four keys with a different value. However, there is an assignment that is possible in the beginning, i.e., { 1, ["A"] }, { 2, ["B"] }, { 3, ["C"] }, { 4, ["D"] }, { 5, ["E"] } and { 6, ["F"] }.



The problem you are trying to solve is fundamentally finding the maximal matching in unweighted bipartite graphs. You can find various algorithms given in that Wikipedia page such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. I will let you figure out how to adjust or extend those algorithms a bit to solve your task of "removing duplicates from dictionary".