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!