The wikipedia entry for disjoint set data structure includes the statement (in the "Applications" section)
Note that the implementation as disjoint-set forests does not allow the deletion of edges, even without path compression or the rank heuristic.
Is the article trying to say that a deletion is not possible with a similar time complexity as the optimized find/union (Inverse Ackermann function as the amortized running time)? Because a blanket statement that deletion is not possible seems like a stretch. There's nothing inherent in the data structure that prevents a deletion operation as long as it restructures the forest. It would be expensive when operating on a non-flattened set, but that isn't the same as not being possible.
Or am I overlooking something that (for instance) would make edge deletion an NP operation?