There is given an undirected graph G = (V, E) from which edges are deleted one at a time. Questions like "Are the vertices u and v in the same connected component?" have to be answered in constant time.