Algorithm to extract the subgraph of all nodes with degree at least four

I have an undirected graph represented by a list of nodes and a list of edges. What I need to produce from this is a list of nodes and edges representing a new graph containing only the nodes which have degree of at least 4. I think I've developed an algorithm. It uses an object called Node, which can store an integer for the degree of the node and a list of that node's neighboring nodes.

• For each node in the graph create a Node object in $O(|V|)$ time and store in a list.

• Traverse the list of edges in $O(|E|)$ time. While doing so update my list of nodes with their appropriate degree and neighbors.

• Search the list in $O(|V|)$ time and find the node with smallest degree. If >4, return. If

• Repeat step 3. At worst $O(|V|)$ times.

If anyone is wondering, I'm doing this for a Civilization-esque game I'm making. I want to be able to separate cities that are part of major trade routes from minor ones.

Now, I think this algorithm is correct, but I'm not happy with its running time. If I'm not mistaken, it's $O(|V|^2)$, correct? Is there a way to make this more efficient?

The object you are trying to find is known in graph theory as the 4-core. Batagelj and Zaveršnik give a simple linear time algorithm for finding the $k$-core for any given $k$.

StackExchange Computer Science Q#40919, answer score: 3