algorithm that removes extraneous connections from a graph
You describe the graph as


$V$ - a set of vertices
$E$ - a set of edges, where each edge is (presumably) an unordered pair. 


To determine where you can go from each vertex $v \in V$, you need to scan the whole of $E$, so you are already $\Theta (|V| + |E|)$. 

If the graph is in the form ...
$$ V \rightarrow 2^V$$
... then you can find a spanning tree in $\Theta(|V|)$. To enumerate the edges left out, you are up to $\Theta (|V| + |E|)$ again. But if you don't need to enumerate them, you can determine whether any given edge is spare in constant time. 



Correction


  If the graph is in the form $ V \rightarrow 2^V$, then you can find a
  spanning tree in $\Theta(|V|)$.


I think this is wrong. Whatever your search order, at each vertex you have to look through the neighbours to find an undiscovered one, which might be the last. Depending on the structure of the graph, this might happen at every vertex. So the worst case at least is $\Theta (|V| + |E|)$.