The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let w t q t u denote the word size, expected query time and worst case update time of a data structure for connectivity on graphs of size n . We provide simplified proofs of the following results:

-- Any data structure for connectivity with error at most 1 32 must have t q log n log w t u . This was proved in the landmark paper of Fredman and Saks \cite{FredmanS89}. -- For every 0"> 0 and data structure for connectivity that makes no errors, if t u = o log n log log n , then t q n 1 − 2 . This was proved by Patrascu and Thorrup in \cite{PatrascuT11}.