# 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.

1. For each node in the graph create a Node object in $O(|V|)$ time and store in a list.
2. Traverse the list of edges in $O(|E|)$ time. While doing so update my list of nodes with their appropriate degree and neighbors.
3. Search the list in $O(|V|)$ time and find the node with smallest degree. If >4, return. If <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.
4. 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?

• Sorry for the lack of clarity. Really I only care about getting the names of the cities in my game, so I need the cities which were essentially part of a "4-clique" from the original graph. Those which had degree at least 4 in the original graph, but only if at least 4 of those neighbors also had degree of at least 4. – user30206 Mar 31 '15 at 19:28
• There are graphs that contain no 4-clique but in which every vertex has degree 4. An example is toroidal grids. Take a chess board, let the squares be vertices and add an edge from each square to the squares that are horizontally and vertically adjacent to it. Also, add edges from the $i$th square in the first row to the $i$th square in the last row, and from the $i$th square in the left column to the $i$th square in the right column, for $i=1..8$. Every vertex has degree 4 but there are no 4-cliques. – David Richerby Mar 31 '15 at 19:43
• Ah, right. That was before I found out 4-core was the term for describing this phenomenon. – user30206 Mar 31 '15 at 19:54

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$.
• Note that this is linear in the number of edges so you can't immediately say that it's better than $O(|V|^2)$. – David Richerby Mar 31 '15 at 19:46
• For my purposes the graphs will always be connected. Since that means $|E| \geq |V| - 1$, $O(|E|)$ should immediately be better than $O(|V|^2)$, no? – user30206 Mar 31 '15 at 19:53
• No, it could be that the graph is complete and so $|E| = |V|^2$. But in practice the number of edges is often much smaller than $|V|^2$, depending on the provenance of the graph. – Yuval Filmus Mar 31 '15 at 19:55
• Ah, I see. So it's not guaranteed to be better, but it almost always will be. And it's still accurate to describe it as $O(|E|)$. Thanks! – user30206 Mar 31 '15 at 19:56