algorithm that removes extraneous connections from a graph For a nondirection graph $G=(V,E)$, I need to write an algorithm that finds connections that can be removed without destroying the graph (ex: a connection from a child of a child back to the root of the graph). I have created an algorithm with a runtime of $O(|V|+|E|)$ (utilizing BFS):

    smallerGraph(G,s):
    for all vertex u from V[G]do
      color[u]=WHITE
      p[u]=NIL
      n[u]=NIL
    end for
    for all vertex u from V[G]do
      if color[u]==WHITE then
        modifiedDFSVisit(G,u)
       end if
    end for
    return 0
    modifiedDFSVisit(G,u):
    color[u]GRAY
    for all vertex v from Adj[u]do
      if color==BLACK and p[v]!=u and p[n[v]]!=v then
        removeLink(u,v)
      end if
      if color[v]==WHITE then
        p[v]=u
        n[u]=v
        modifiedDFSVisit(G,v)
      end if
    end for
    color[u]=BLACK


Additionally, I am also looking algorithm that can solve the same problem, however this time with a runtime of $O(|V|)$. If this is possible, if someone could point me in the right direction, I would appreciate it. If it isn't possible, why? Would the answer change if I was given a list of the connections (as well as the number of connections)?
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|)$.