Find maximal subgraph containing only nodes of degree 2 and 3 I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to compute a maximal 2-3 subgraph of the input graph.

To be precise, a 2-3 graph is one that has only vertices of degree either 2 or 3. By maximal we mean that there is no other 2-3 subgraph which contains the maximal subgraph as a proper subgraph. It does not have to be a maximum subgraph.

The authors of the paper claim that the computation can be carried out by a simple Depth First Search (DFS) on the graph. However, this algorithm seems to elude me. How can the maximal subgraph be computed?
Basically, in 2-3 graph, the lower bound 2 means that any node has to be in a cycle. 

In DFS, when you reach an already visited node, you found a cycle. Just check if adding this cycle to your subgraph also respect the upper bound 3.

As you suggested, the maximal 2-3 subgraph is not unique. But if you built it following this method, you ensure that any node/vertex of $G$ you did not select in your subgraph:


either is not part of any cycle and would lead to a vertex of degree 1 if selected
either is part of cycles that would all lead to a vertex of degree 4 if selected


Thus, your 2-3 subgraph is maximal.