Verifying connectivity of a graph in O(n^2)
You can do one graph traversal to find all the connected components of your graph.

Then add an edge from each connected component to the next : the graph is fully connected and you did only one traversal, that's $O(n^2)$