Vertex deletion to perfect matching You are given a Graph G and an integer k.

The question is: Does G contain a vertex set X of size at most k such that deleting X results in a graph of degree at most 1?

Design an FPT (or a kernelization) algorithm for this problem and argue why it is correct.

Hint: Observe that vertices of higher degree must be "dealt with" somehow.

I do not exactly know where to start. I suppose that some reduction rules can be applied first, but not so sure what those can be (probably something that "deals with" vertices of higher degree.

Any ideas?
I'm not sure about the FPT algorithm, but I have an idea for the kernelization.

All vertices with degree > k + 1 must be in X, since otherwise you would have to pick all but one of its neighbours which would make |X| > k. So you can delete a vertex with degree > k + 1 and rerun the algorithm with the remaining graph and k = k - 1.

You can also delete any vertices with degree 0, as their deletion doesn't change the degree of any other vertices.