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 &lt;4, visit the node's neighbors, reduce their degrees by one, and remove this node from their list of neighbors. Then remove this node from the graph, in worst case $O(|V|)$ time.
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$.