# Reduction rules to lower bound minimum degree of a graph

I'm trying to come up with a list of rules that return an equivalent instance to the following problem, while eliminating all vertices of degree 2 or less from the graph:

Given a graph $$G=(V,E)$$, the goal is to know if there's a set $$S\subseteq V$$ of size at most $$k$$ such that $$G-S$$ is an Almost Forest.

An almost forest is a graph where every component is either a tree or a cycle.

So given any graph (multi-graph) and $$k$$: $$(G,k)$$

I know I can remove any component that's either a tree or a cycle, that includes isolated vertices and the graph obtained has a solution $$S\subseteq V'$$ of size at most $$k$$ iff the original graph has a solution of size at most $$k$$.

That eliminates all vertices of degree 0.

The problem with vertices of degree 1(leaves) is:

Suppose $$v\in V$$ is a leaf and let $$u\in V$$ be it's only neighbor. if $$u$$ is part of a cycle $$C$$ then $$C$$ is not a component so we must remove either $$v$$ or a vertex from $$C$$ to obtain an almost forest. If we delete $$v$$ we obtain a cycle(and possibly other vertices attached to it, and chords within it). If $$C$$ becomes a component then this is the best we could've done and picking $$v$$ was a smart choice so we reduce it to $$(G-v,k-1)$$. But if $$C$$ still has chords for example within it, it might have been smarter to delete some other vertex from $$C$$ that is an endpoint of the chord in $$C$$, so the reduction performed by picking $$v$$ is incorrect. Also as stated before $$v$$ might actually be a part of the solution so it definitely is not correct to reduce the instance to $$(G-v,k)$$. It seems as if it's impossible to remove leaves..

I'd love any ideas I can get..

• cs.stackexchange.com/q/141786/755
– D.W.
Commented Jul 10, 2021 at 22:46
• @D.W. I'm not asking the same thing. This is the same problem but I'm not talking about runtime complexity or an algorithm to solve the problem. Commented Jul 11, 2021 at 5:50
• Yes, thank you, I'm aware - that's why it is not marked as a duplicate.
– D.W.
Commented Jul 11, 2021 at 6:36