Problem

Given a simple, undirected graph G = (V, E), where |V| = n = number of nodes and |E| = m = number of edges, check whether G is triconnected. That is, whether G remains connected (a path exists from each node to all the other nodes) after randomly removing any two edges. Required time complexity: O(n^2(n + m))

My solution

For each node in G do the following:

1. Check whether the node has at least 3 edges to 3 different nodes: O(1).

2. Ignore the node and run depth-first search on the remaining graph to check whether it is still connected: O(n + m)

Time complexity: O(n(n + m)) = O(n^2(n + m)).

Is my solution correct?

No, consider the graph with vertices X and *.

  *   *
 /|\ /|\
*-+-X-+-*
 \|/ \|/
  *   *

This graph is 3-edge-connected but if you delete X, it's disconnected.