Finding the nodes that have degree at least 3 in an undirected graph

I want to come up with a good algorithm that takes as input an undirected graph $G$ and checks which vertices to include in an output graph $G'$, such that each vertex in $G'$ has degree at least 3.

I've thought about traversing the graph once to eliminate any vertex with degree less than 3 since none of these can be included in the output. Then, I could have a set $S$ that initially contains some arbitrary vertex that hasn't been eliminated; the rest of the vertices are kept in the set $T$.

If I keep with this idea, I'm not sure how to start moving in vertices from $T$ to $S$ and at which point to delete them. I also wonder if there's a way to use BFS to scan and see if each vertex has degree at least three in the output tree of the BFS procedure. Any pointers/ideas would be appreciated; thanks!

This problem is known as a maximum $k$- core (in your case $k = 3$) and can be solved in polytime. The idea is the one you mentioned : simply delete vertex with degree less than 3 until you don't have such vertices.

More accurate description of the algorithm:

Store your graph as adjacency list. Whenever you find a vertex with degree less than $k$ mark it as deleted and then remove it from neighbors list of its neighbors. In the end you can shift indices if you really need them to be in consecutive order.

StackExchange Computer Science Q#71351, answer score: 2