a graph exercise

From Dasgupta's Algorithms book.

Given an undirected graph, find a subgraph such that each vertex has at least 5 neighbors and at least 5 non-neighbors.

This is a simple problem but it took me an afternoon to figure out the algorithm.

Disclaimer: my solution may not be the most efficient, nor does it represents a consent from the authors for being correct.

The whole idea is about degree. Let deg(v) be the degree of vertex v in current graph. We know that in the final graph, all deg(v) must be
5 <= deg(v) <= n-6
the >=5 is obvious, the n-6 upper bound comes from the need to have 5 non-neighbors.

A simple observation is that if the input graph G has all vertex v with deg(v) within bound, then we are done. Otherwise there is at least one vertex violating the bound. To convert any graph G into a graph with only valid vertex (deg within bounds), we repeat the two operations until done:

1. Remove all vertex v with deg(v) <=4, until no such vertex available.
2. Remove all vertex v with deg(v) >=n-5, until no such vertex available.

op 1 is obvious, if v has deg<=4, then it can never have deg>=5 if we remove other vertices.

op 2 is for a similar reason, if a vertex has deg>=n-5, that implies it has less than 5 non-neighbors. Because we only remove vertex, removing other vertex cannot make v have more non-neighbors. So we have to remove v from the graph to make all vertices valid.

For complexity, we do at most |V| iterations, each iteration takes O(|V|+|E|) time to count deg for each vertex, for a total of (|V|^2 + |V||E|)