Check if graph stays connected after edge swap Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after repeated modifications, specifically: repeated edge swaps. An edge swap removes two edges $\{a - b, c-d\}$ and adds $\{a-c, b-d\}$ instead.  Is there a way to do better than a full linear-time check after each and every modification?
Check this paper https://arxiv.org/pdf/1209.5608.pdf which uses cluster forest which support operations like:

connected(u, v) : if vertex u and v are connected , 
insert(u, v) : Insert edge (u, v) 
delete(u, v) : delete edge (u, v) 

It answers your query in O(log n / log log n) time with O(log2n / log log n) update time.